3.1.3 FlowMiner
How can expressive, compact information flow summaries be mined from a library for accurate and scalable partial program analysis?
Our research to address this question has led a technological advance for analyzing programs that depend on software libraries.
Static program analysis tools are critical to the field of software engineering, allowing us to compile, refactor, verify, and understand our code. Because modern software is built on top of reusable libraries and frameworks, whole program analysis is prohibitively expensive; hence tools must instead perform partial program analysis - analysis of a proper subset of a program's implementation. Missing data flow semantics of these components introduce problematic gaps for many use cases, including security-critical analyses. Prior attempts to overcome this, including hand-written models, heuristics, and dynamically inferred specifications, are too coarse for many analysis use cases, introducing inaccuracies.
Supported by the additional seed funding in 2014, we started developing FlowMiner, a tool to mine expressive data flow summaries from Java library binaries to enable complete and accurate partial program analysis. This work was recently completed and it is a part of Tom Deering’s Ph.D. research. As far as we know, we are the first to create fine-grained summaries that can be used in a context, type, field, object and flow-sensitive manner. We also emphasize compaction – flow details that are not critical for accurate use are elided into simple edges between elements that are accuracy-critical. As a result, summaries extracted by FlowMiner are an order of magnitude smaller than the original library in size. The salient features of our technique are: (i) novel algorithms to extract fine-grained summary data flow semantics from a Java library, (ii) compactness of the summaries with respect to the original libraries, (iii) graph summarization paradigm that uses a multi-attributed directed graph as the mathematical abstraction to store summaries, (iv) open-source implementation (FlowMiner) of the above that saves summaries in a portable format usable by existing analysis tools, and (v) validation of our work by on some of the most popular Java libraries. We discuss the characteristics of our summaries versus those from other state-of-the-art tooling. We also demonstrate that our work allows our existing analysis tools to accurately handle previously unaddressed data flows in Android applications.
3.1.3.1 Balancing Expressiveness and Compactness
When summarizing the data flow semantics of a library, certain key artifacts in the library will be crucial to its data flow. For example, individual field definitions must be present if a summary is to be used in a field-sensitive way, and individual call sites must be preserved if library callbacks are to be captured. For example, we empirically show that 93.07% of summarized field flows will be false positives if field definitions are not retained. Consequently, fields, method call sites, literal values, and formal and informal method parameters and return values are all key artifacts of a flow that must be preserved in a summary data flow.
On the other hand, non-key features such as some def-use chains of assignments do not add value to the paths in which they participate, and can be abstracted away in the summary. FlowMiner elides (replaces paths with direct edges) uninteresting flow details to arrive at an abstract data flow graph that contains the key artifacts crucial to the data flow and reachability information between them, and is much more compact than the original program graph. This allows us to achieve significant savings and enhanced scalability versus the original library, while preserving soundness. In other words, the flows that are preserved in FlowMiner's summary are precisely those that are actually possible at runtime.
3.1.3.2 Validation
We have validated FlowMiner by demonstrating that our summaries of popular libraries are much smaller than the original programs, yet more expressive and accurate than other state-of-the-art summary techniques. We find that our summaries only contain 26.89% of the nodes and 16.32% of the edges of the original library program graphs, on average.
3.1.3.3 Open Source
We provide FlowMiner, an open-source reference implementation of our algorithms that extracts summaries given the source or byte code of a library and exports them to a portable, tool-agnostic format. The FlowMiner research is described in more detail in Tom Deering’s Ph.D. thesis and a paper based on this work will be submitted for publication. The tool is available at the following site: http://powerofpi.github.io/FlowMiner/