We consider the problem of recovering program structure from compiled binary code. We first extract the call graph and layout of functions in memory from the compiled code and represent this information in a graphical format. We then employ Louvain's modularity algorithm to identify clusters of functions that are considered to be related. We find that the quality and properties of clusters extracted by our technique are greatly impacted by the relative importance we assign to the call graph and the ordering of functions in memory.
We discuss the challenges and approaches to securing numeric computation against adversaries who may want to discover hidden parameters or values used by the algorithm. We discuss techniques that are both cryptographic and non-cryptographic in nature. Cryptographic solutions are either not yet algorithmically feasible or currently require more computational resources than are reasonable to have in a deployed setting. Non-cryptographic solutions may be computationally faster, but these cannot stop a determined adversary. For one such non-cryptographic solution, mixed Boolean arithmetic, we suggest a number of improvements that may protect the obfuscated calculation against current automated deobfuscation methods.
In practical applications of automated terrain classification from high-resolution polarimetric synthetic aperture radar (PolSAR) imagery, different terrain types may inherently contain a high level of internal variability, as when a broadly defined class (e.g., 'trees') contains elements arising from multiple subclasses (pine, oak, and willow). In addition, real-world factors such as the time of year of a collection, the moisture content of the scene, the imaging geometry, and the radar system parameters can all increase the variability observed within each class. Such variability challenges the ability of classifiers to maintain a high level of sensitivity in recognizing diverse elements that are within-class, without sacrificing their selectivity in rejecting out-of-class elements. In an effort to gauge the degree to which classifiers respond robustly in the presence of intraclass variability and generalize to untrained scenes and conditions, we compare the performance of a suite of classifiers across six broad terrain categories from a large set of polarimetric synthetic aperture radar (PolSAR) image sets. The main contributions of this article are as follows: 1) an analysis of the robustness of a variety of current state-of-the art classification algorithms to intraclass variability found in PolSAR image sets, and 2) the associated PolSAR image and feature data that Sandia is releasing to the research community with this publication. The analysis of the classification algorithms we provide will serve as a benchmark of performance for the future PolSAR terrain classification algorithm research and development enabled by the image sets and data provided. By sharing our analysis and high-resolution fully polarimetric Sandia data with the research community, we enable others to develop and assess a new generation of robust terrain classification algorithms for PolSAR.
Social network graph models are data structures representing entities (often people, corporations, or accounts) as "vertices" and their interactions as "edges" between pairs of vertices. These graphs are most often total-graph models — the overall structure of edges and vertices in a bidirectional or directional graph are described in global terms and the network is generated algorithmically. We are interested in "egocentrie or "agent-based" models of social networks where the behavior of the individual participants are described and the graph itself is an emergent phenomenon. Our hope is that such graph models will allow us to ultimately reason from observations back to estimated properties of the individuals and populations, and result in not only more accurate algorithms for link prediction and friend recommendation, but also a more intuitive understanding of human behavior in such systems than is revealed by previous approaches. This report documents our preliminary work in this area; we describe several past graph models, two egocentric models of our own design, and our thoughts about the future direction of this research.
Here, we develop a method for time-dependent topic tracking and meme trending in social media. Our objective is to identify time periods whose content differs signifcantly from normal, and we utilize two techniques to do so. The first is an information-theoretic analysis of the distributions of terms emitted during different periods of time. In the second, we cluster documents from each time period and analyze the tightness of each clustering. We also discuss a method of combining the scores created by each technique, and we provide ample empirical analysis of our methodology on various Twitter datasets.
We present findings on the computational complexity of computing multidimensional persistent homology. We first show that the worst-case computational complexity of multidimensional persistence is exponential. We then present an algorithm for computing multidimensional persistence which extends the algorithm given by Zomorodian and Carlsson for computing one-dimensional persistence. The computational complexity of our algorithm is polynomial in the size of the persistence module and exponential in the persistence dimension.
Topological data analysis is the study of data using techniques from algebraic topology. Often, one begins with a finite set of points representing data and a “filter” function which assigns a real number to each datum. Using both the data and the filter function, one can construct a filtered complex for further analysis. For example, applying the homology functor to the filtered complex produces an algebraic object known as a “one-dimensional persistence module”, which can often be interpreted as a finite set of intervals representing various geometric features in the data. If one runs the above process incorporating multiple filter functions simultaneously, one instead obtains a multidimensional persistence module. Unfortunately, these are much more difficult to interpret. In this article, we analyze the space of multidimensional persistence modules from the perspective of algebraic geometry. We first build a moduli space of a certain subclass of easily analyzed multidimensional persistence modules, which we construct specifically to capture much of the information which can be gained by using multidimensional persistence instead of one-dimensional persistence. We argue that the global sections of this space provide interesting numeric invariants when evaluated against our subclass of multidimensional persistence modules. Finally, we extend these global sections to the space of all multidimensional persistence modules and discuss how the resulting numeric invariants might be used to study data. This paper extends the results of Adcock et al. (Homol Homotopy Appl 18(1), 381–402, 2016) by constructing numeric invariants from the computation of a multidimensional persistence module as given by Carlsson et al. (J Comput Geom 1(1), 72–100, 2010).
In this work, we approach topic tracking and meme trending in social media with a temporal focus; rather than analyzing topics, we aim to identify time periods whose content differs significantly from normal. We detail two approaches. The first is an information-theoretic analysis of the distributions of terms emitted during each time period. In the second, we cluster the documents from each time period and analyze the tightness of each clustering. We also discuss a method of combining the scores created by each technique, and we provide ample empirical analysis of our methodology on various Twitter datasets.
In this paper, we analyze the space of multidimensional persistence modules from the perspectives of algebraic geometry. We first build a moduli space of a certain subclass of easily analyzed multidimensional persistence modules, which we construct specifically to capture much of the information which can be gained by using multidimensional persistence over one-dimensional persistence. We argue that the global sections of this space provide interesting numeric invariants when evaluated against our subclass of multidimensional persistence modules. Lastly, we extend these global sections to the space of all multidimensional persistence modules and discuss how the resulting numeric invariants might be used to study data.