skip to main content


Title: Towards Automatically Generating a Sound and Complete Dataset for Evaluating Static Analysis Tools
Binary static analysis has seen a recent surge in interest, due to a rise in analysis targets for which no other method is appropriate, such as, embedded firmware. This has led to the proposal of a number of binary static analysis tools and techniques, handling various kinds of programs, and answering different research questions. While static analysis tools that focus on binaries inherit the undecidability of static analysis, they bring with them other challenges, particularly in dealing with the aliasing of code and data pointers. These tools may tackle these challenges in different ways, but unfortunately, there is currently no concrete means of comparing their effectiveness at solving these central, problem-independent aspects of static analysis. In this paper, we propose a new method for creating a dataset of real-world programs, paired with the ground truth for static analysis. Our approach involves the injection of synthetic “facts” into a set of open-source programs, consisting of new variables and their possible values. The analyses’ goal is then to evaluate the possible values of these facts at certain program points. As the facts are injected randomly within an arbitrarily-large set of programs, the kinds of data flows that can be measured are widely-varied in size and complexity. We implemented this idea as a prototype system, AUTOFACTS, and used it to create a ground truth dataset of 29 programs, with various types and number of facts, resulting in a total of 2,088 binaries (with 72 versions for each program). To our knowledge, this is the first dataset aimed at the problem-independent evaluation of static analysis tools, and we contribute all code and the dataset itself to the community as open-source.  more » « less
Award ID(s):
1704253
NSF-PAR ID:
10155111
Author(s) / Creator(s):
; ; ; ; ;
Date Published:
Journal Name:
Workshop on Binary Analysis Research (BAR)
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Human analysts must reverse engineer binary programs as a prerequisite for a number of security tasks, such as vulnerability analysis, malware detection, and firmware re-hosting. Existing studies of human reversers and the processes they follow are limited in size and often use qualitative metrics that require subjective evaluation. In this paper, we reframe the problem of reverse engineering binaries as the problem of perfect decompilation, which is the process of recovering, from a binary program, source code that, when compiled, produces binary code that is identical to the original binary. This gives us a quantitative measure of understanding, and lets us examine the reversing process programmatically. We developed a tool, called Decomperson, that supported a group of reverse engineers during a large-scale security competition designed to collect information about the participants' reverse engineering process, with the well-defined goal of achieving perfect decompilation. Over 150 people participated, and we collected more than 35,000 code submissions, the largest manual reverse engineering dataset to date. This includes snapshots of over 300 successful perfect decompilation attempts. In this paper, we show how perfect decompilation allows programmatic analysis of such large datasets, providing new insights into the reverse engineering process. 
    more » « less
  2. Software depends on upstream projects that regularly fix vulnerabilities, but the documentation of those vulnerabilities is often unreliable or unavailable. Automating the collection of existing vulnerability fixes is essential for downstream projects to reliably update their dependencies due to the sheer number of dependencies in modern software. Prior efforts rely solely on incomplete databases or imprecise or inaccurate statistical analysis of upstream repositories. In this paper, we introduce Differential Alert Analysis (DAA) to discover vulnerability fixes in software projects. In contrast to statistical analysis, DAA leverages static analysis security testing (SAST) tools, which reason over code context and semantics. We provide a language-independent implementation of DAA and show that for Python and Java based projects, DAA has high precision for a ground-truth dataset of vulnerability fixes — even with noisy and low-precision SAST tools. We then use DAA in two large-scale empirical studies covering several prominent ecosystems, finding hundreds of resolved alerts, including many never publicly disclosed. DAA thus provides a powerful, accurate primitive for software projects, code analysis tools, vulnerability databases, and researchers to characterize and enhance the security of software supply chains. 
    more » « less
  3. The key challenge of software reverse engi- neering is that the source code of the program under in- vestigation is typically not available. Identifying differ- ences between two executable binaries (binary diffing) can reveal valuable information in the absence of source code, such as vulnerability patches, software plagiarism evidence, and malware variant relations. Recently, a new binary diffing method based on symbolic execution and constraint solving has been proposed to look for the code pairs with the same semantics, even though they are ostensibly different in syntactics. Such semantics- based method captures intrinsic differences/similarities of binary code, making it a compelling choice to analyze highly-obfuscated malicious programs. However, due to the nature of symbolic execution, semantics-based bi- nary diffing suffers from significant performance slow- down, hindering it from analyzing large numbers of malware samples. In this paper, we attempt to miti- gate the high overhead of semantics-based binary diff- ing with application to malware lineage inference. We first study the key obstacles that contribute to the performance bottleneck. Then we propose normalized basic block memoization to speed up semantics-based binary diffing. We introduce an unionfind set structure that records semantically equivalent basic blocks. Managing the union-find structure during successive comparisons allows direct reuse of previously computed results. Moreover, we utilize a set of enhanced optimization methods to further cut down the invocation numbers of constraint solver. We have implemented our tech- nique, called MalwareHunt, on top of a trace-oriented binary diffing tool and evaluated it on 15 polymorphic and metamorphic malware families. We perform intra- family comparisons for the purpose of malware lineage inference. Our experimental results show that Malware- Huntcan accelerate symbolic execution from 2.8X to 5.3X (with an average 4.1X), and reduce constraint solver invocation by a factor of 3.0X to 6.0X (with an average 4.5X). 
    more » « less
  4. Nicewonger, Todd E. ; McNair, Lisa D. ; Fritz, Stacey (Ed.)
    https://pressbooks.lib.vt.edu/alaskanative/ At the start of the pandemic, the editors of this annotated bibliography initiated a remote (i.e., largely virtual) ethnographic research project that investigated how COVID-19 was impacting off-site modular construction practices in Alaska Native communities. Many of these communities are located off the road system and thus face not only dramatically higher costs but multiple logistical challenges in securing licensed tradesmen and construction crews and in shipping building supplies and equipment to their communities. These barriers, as well as the region’s long winters and short building seasons, complicate the construction of homes and related infrastructure projects. Historically, these communities have also grappled with inadequate housing, including severe overcrowding and poor-quality building stock that is rarely designed for northern Alaska’s climate (Marino 2015). Moreover, state and federal bureaucracies and their associated funding opportunities often further complicate home building by failing to accommodate the digital divide in rural Alaska and the cultural values and practices of Native communities.[1] It is not surprising, then, that as we were conducting fieldwork for this project, we began hearing stories about these issues and about how the restrictions caused by the pandemic were further exacerbating them. Amidst these stories, we learned about how modular home construction was being imagined as a possible means for addressing both the complications caused by the pandemic and the need for housing in the region (McKinstry 2021). As a result, we began to investigate how modular construction practices were figuring into emergent responses to housing needs in Alaska communities. We soon realized that we needed to broaden our focus to capture a variety of prefabricated building methods that are often colloquially or idiomatically referred to as “modular.” This included a range of prefabricated building systems (e.g., manufactured, volumetric modular, system-built, and Quonset huts and other reused military buildings[2]). Our further questions about prefabricated housing in the region became the basis for this annotated bibliography. Thus, while this bibliography is one of multiple methods used to investigate these issues, it played a significant role in guiding our research and helped us bring together the diverse perspectives we were hearing from our interviews with building experts in the region and the wider debates that were circulating in the media and, to a lesser degree, in academia. The actual research for each of three sections was carried out by graduate students Lauren Criss-Carboy and Laura Supple.[3] They worked with us to identify source materials and their hard work led to the team identifying three themes that cover intersecting topics related to housing security in Alaska during the pandemic. The source materials collected in these sections can be used in a variety of ways depending on what readers are interested in exploring, including insights into debates on housing security in the region as the pandemic was unfolding (2021-2022). The bibliography can also be used as a tool for thinking about the relational aspects of these themes or the diversity of ways in which information on housing was circulating during the pandemic (and the implications that may have had on community well-being and preparedness). That said, this bibliography is not a comprehensive analysis. Instead, by bringing these three sections together with one another to provide a snapshot of what was happening at that time, it provides a critical jumping off point for scholars working on these issues. The first section focuses on how modular housing figured into pandemic responses to housing needs. In exploring this issue, author Laura Supple attends to both state and national perspectives as part of a broader effort to situate Alaska issues with modular housing in relation to wider national trends. This led to the identification of multiple kinds of literature, ranging from published articles to publicly circulated memos, blog posts, and presentations. These materials are important source materials that will likely fade in the vastness of the Internet and thus may help provide researchers with specific insights into how off-site modular construction was used – and perhaps hyped – to address pandemic concerns over housing, which in turn may raise wider questions about how networks, institutions, and historical experiences with modular construction are organized and positioned to respond to major societal disruptions like the pandemic. As Supple pointed out, most of the material identified in this review speaks to national issues and only a scattering of examples was identified that reflect on the Alaskan context. The second section gathers a diverse set of communications exploring housing security and homelessness in the region. The lack of adequate, healthy housing in remote Alaska communities, often referred to as Alaska’s housing crisis, is well-documented and preceded the pandemic (Guy 2020). As the pandemic unfolded, journalists and other writers reported on the immense stress that was placed on already taxed housing resources in these communities (Smith 2020; Lerner 2021). The resulting picture led the editors to describe in their work how housing security in the region exists along a spectrum that includes poor quality housing as well as various forms of houselessness including, particularly relevant for the context, “hidden homelessness” (Hope 2020; Rogers 2020). The term houseless is a revised notion of homelessness because it captures a richer array of both permanent and temporary forms of housing precarity that people may experience in a region (Christensen et al. 2107). By identifying sources that reflect on the multiple forms of housing insecurity that people were facing, this section highlights the forms of disparity that complicated pandemic responses. Moreover, this section underscores ingenuity (Graham 2019; Smith 2020; Jason and Fashant 2021) that people on the ground used to address the needs of their communities. The third section provides a snapshot from the first year of the pandemic into how CARES Act funds were allocated to Native Alaska communities and used to address housing security. This subject was extremely complicated in Alaska due to the existence of for-profit Alaska Native Corporations and disputes over eligibility for the funds impacted disbursements nationwide. The resources in this section cover that dispute, impacts of the pandemic on housing security, and efforts to use the funds for housing as well as barriers Alaska communities faced trying to secure and use the funds. In summary, this annotated bibliography provides an overview of what was happening, in real time, during the pandemic around a specific topic: housing security in largely remote Alaska Native communities. The media used by housing specialists to communicate the issues discussed here are diverse, ranging from news reports to podcasts and from blogs to journal articles. This diversity speaks to the multiple ways in which information was circulating on housing at a time when the nightly news and radio broadcasts focused heavily on national and state health updates and policy developments. Finding these materials took time, and we share them here because they illustrate why attention to housing security issues is critical for addressing crises like the pandemic. For instance, one theme that emerged out of a recent National Science Foundation workshop on COVID research in the North NSF Conference[4] was that Indigenous communities are not only recovering from the pandemic but also evaluating lessons learned to better prepare for the next one, and resilience will depend significantly on more—and more adaptable—infrastructure and greater housing security. 
    more » « less
  5. Call graph or caller-callee relationships have been used for various kinds of static program analysis, performance analysis and profiling, and for program safety or security analysis such as detecting anomalies of program execution or code injection attacks. However, different tools generate call graphs in different formats, which prevents efficient reuse of call graph results. In this paper, we present an approach of using ontology and resource description framework (RDF) to create knowledge graphs for specifying call graphs to facilitate the construction of full-fledged and complex call graphs of computer programs, realizing more interoperable and scalable program analyses than conventional approaches. We create a formal ontology-based specification of call graph information to capture concepts and properties of both static and dynamic call graphs so different tools can collaboratively contribute to more comprehensive analysis results. Our experiments show that ontology enables merging of call graphs generated from different tools and flexible queries using a standard query interface. 
    more » « less