Alias analysis is a technique to identify whether a memory location can be accessed in more than one way. An ideal alias analysis implementation should be both precise and scalable. However, in practice, implementations of alias analysis have to make a trade-off between precision and scalability. The alias analysis implementations that perform inter-procedural analysis are more precise (answer a higher number of alias queries with certainty), but expensive, making them infeasible for practical use. Most compiler developers opt for intra-procedural analysis over inter-procedural, thereby compromising the precision of alias analysis implementations to achieve scalability. For compilers, this compromise leads to a loss in optimization opportunities, limiting the performance achievable by the compiled program.

Advances in Artificial Intelligence (AI), and in particular in Machine Learning (ML), are introducing profound changes to scholarly submissions across publication venues, affecting in particular the contributions that are being submitted to Software Engineering (SE) conferences and journals. In this context, it is not always clear whether manuscripts submitted to SE venues under the umbrella term SE for AI are indeed relevant to SE, in the sense that they explicitly contain contributions to the SE body of knowledge. This leads to recurring discussions on whether certain AI-related submissions are appropriate to SE venues, or should instead be submitted to other journals and conferences, including AI or ML-specific ones. In this editorial, we discuss the kinds of AI-related contributions that are a better fit-and a less good fit-for publication in the IEEE Transactions on Software Engineering.

Concurrency errors due to poorly handled exceptions are common. Developers often make mistakes in writing proper code logic to relinquish the resources in the exception-handlers and cleanup blocks such as finally in Java. Our observations suggest that these mistakes often go unnoticed because the exception-handling code is generally not tested in the development phase. These errors materialize when the exception handlers execute within the production environment. Therefore, verifying multi-threaded programs augmented with their exception handlers is necessary to guarantee their correctness. This paper proposes a dynamic technique to verify exception-handling code in concurrent libraries. The technique detects the presence of deadlocks originating from exception-handling code. We also present a prototype called Lumina,that implements our technique to demonstrate that it can detect the deadlocks effectively, unlike the state-of-the-art dynamic verifier JavaPathfinder (JPF).

Spatial safety violations are the root cause of many security attacks and unexpected behavior of applications. Existing techniques to enforce spatial safety work broadly at either object or pointer granularity. Object-based approaches tend to incur high CPU overheads, whereas pointer-based approaches incur both high CPU and memory overheads. SGXBounds, an object-based approach, provides precise out-of-bounds protection for objects at a lower overhead compared to other tools with similar precision. However, a major drawback of this approach is that it cannot support address space larger than 32-bit.

Interprocedural alias analyses often sacrifice precision for scalability. Thus, modern compilers such as GCC and LLVM implement more scalable but less precise intraprocedural alias analyses. This compromise makes the compilers miss out on potential optimization opportunities, affecting the performance of the application. Modern compilers implement loop-versioning with dynamic checks for pointer disambiguation to enable the missed optimizations. Polyhedral access range analysis and symbolic range analysis enable 𝑂 (1) range checks for non-overlapping of memory accesses inside loops. However, these approaches work only for the loops in which the loop bounds are loop invariants. To address this limitation, researchers proposed a technique that requires 𝑂 (𝑙𝑜𝑔 𝑛) memory accesses for pointer disambiguation. Others improved the performance of dynamic checks to single memory access by constraining the object size and alignment. However, the former approach incurs noticeable overhead due to its dynamic checks, whereas the latter has a noticeable allocator overhead. Thus, scalability remains a challenge. In this work, we present a tool, Rapid, that further reduces the overheads of the allocator and dynamic checks proposed in the existing approaches. The key idea is to identify objects that need disambiguation checks using a profiler and allocate them in different regions, which are disjoint memory areas. The disambiguation checks simply compare the regions corresponding to the objects. The regions are aligned such that the top 32 bits in the addresses of any two objects allocated in different regions are always different. As a consequence, the dynamic checks do not require any memory access to ensure that the objects belong to different regions, making them efficient. Rapid achieved a maximum performance benefit of around 52.94% for Polybench and 1.88% for CPU SPEC 2017 benchmarks. The maximum CPU overhead of our allocator is 0.57% with a geometric mean of -0.2% for CPU SPEC 2017 benchmarks. Due to the low overhead of the allocator and dynamic checks, Rapid could improve the performance of 12 out of 16 CPU SPEC 2017 benchmarks. In contrast, a state-of-the-art approach used in the comparison could improve only five CPU SPEC 2017 benchmarks.

Code clone detection is an important aspect of software development and maintenance. The extensive research in this domain has helped reduce the complexity and increase the robustness of source code, thereby assisting bug detection tools. However, the majority of the clone detection literature is confined to a single language. With the increasing prevalence of cross-platform applications, functionality replication across multiple languages is common, resulting in code fragments having similar functionality but belonging to different languages. Since such clones are syntactically unrelated, single language clone detection tools are not applicable in their case. In this article, we propose a semi-supervised deep learning-based toolRubhus, capable of detecting clones across different programming languages.Rubhususes the control and data flow enriched abstract syntax trees (ASTs) of code fragments to leverage their syntactic and structural information and then applies graph neural networks (GNNs) to extract this information for the task of clone detection. We demonstrate the effectiveness of our proposed system through experiments conducted over datasets consisting of Java, C, and Python programs and evaluate its performance in terms of precision, recall, and F1 score. Our results indicate thatRubhusoutperforms the state-of-the-art cross-language clone detection tools.

Context-sensitive inter-procedural alias analyses are more precise than intra-procedural alias analyses. However, context-sensitive inter-procedural alias analyses are not scalable. As a consequence, most of the production compilers sacrifice precision for scalability and implement intra-procedural alias analysis. The alias analysis is used by many compiler optimizations, including loop transformations. Due to the imprecision of alias analysis, the program’s performance may suffer, especially in the presence of loops. Previous work proposed a general approach based on code-versioning with dynamic checks to disambiguate pointers at runtime. However, the overhead of dynamic checks in this approach is O(log n), which is substantially high to enable interesting optimizations. Other suggested approaches, e.g., polyhedral and symbolic range analysis, have O(1) overheads, but they only work for loops with certain constraints. The production compilers, such as LLVM and GCC, use scalar evolution analysis to compute an O(1) range check for loops to resolve memory dependencies at runtime. However, this approach also can only be applied to loops with certain constraints. In this work, we present our tool, Scout, that can disambiguate two pointers at runtime using single memory access. Scout is based on the key idea to constrain the allocation size and alignment during memory allocations. Scout can also disambiguate array accesses within a loop for which the existing O(1) range checks technique cannot be applied. In addition, Scout uses feedback from static optimizations to reduce the number of dynamic checks needed for optimizations. Our technique enabled new opportunities for loop-invariant code motion, dead store elimination, loop vectorization, and load elimination in an already optimized code. Our performance improvements are up to 51.11% for Polybench and up to 0.89% for CPU SPEC 2017 suites. The geometric means for our allocator’s CPU and memory overheads for CPU SPEC 2017 benchmarks are 1.05%, and 7.47%, respectively. For Polybench benchmarks, the geometric mean of CPU and memory overheads are 0.21% and 0.13%, respectively.

Instruction reordering and interleavings in program execution under relaxed memory semantics result in non-intuitive behaviors, making it difficult to provide assurances about program correctness. Studies have shown that up to 90% of the concurrency bugs reported by state-of-the-art static analyzers are false alarms. As a result, filtering false alarms and detecting real concurrency bugs is a challenging problem. Unsurprisingly, this problem has attracted the interest of the research community over the past few decades. Nonetheless, many of the existing techniques rely on analyzing source code, rarely consider the effects introduced by compilers, and assume a sequentially consistent memory model. In a practical setting, however, developers often do not have access to the source code, and even commodity architectures such as x86 and ARM are not sequentially consistent. In this work, we present B i rd , a prototype tool, to dynamically detect harmful data races in x86 binaries under relaxed memory models, TSO and PSO. B i rd employs source-DPOR to explore all distinct feasible interleavings for a multithreaded application. Our evaluation of B i rd on 42 publicly available benchmarks and its comparison with the state-of-the-art tools indicate B i rd ’s potential in effectively detecting data races in software binaries.

Code clones are duplicate code fragments that share (nearly) similar syntax or semantics. Code clone detection plays an important role in software maintenance, code refactoring, and reuse. A substantial amount of research has been conducted in the past to detect clones. A majority of these approaches use lexical and syntactic information to detect clones. However, only a few of them target semantic clones. Recently, motivated by the success of deep learning models in other fields, including natural language processing and computer vision, researchers have attempted to adopt deep learning techniques to detect code clones. These approaches use lexical information (tokens) and(or) syntactic structures like abstract syntax trees (ASTs) to detect code clones. However, they do not make sufficient use of the available structural and semantic information, hence limiting their capabilities. This paper addresses the problem of semantic code clone detection using program dependency graphs and geometric neural networks, leveraging the structured syntactic and semantic information. We have developed a prototype toolHolmes, based on our novel approach and empirically evaluated it on popular code clone benchmarks. Our results show thatHolmesperforms considerably better than the other state-of-the-art tool, TBCCD. We also assessedHolmeson unseen projects and performed cross dataset experiments to evaluate the generalizability ofHolmes. Our results affirm thatHolmesoutperforms TBCCD since most of the pairs thatHolmesdetected were either undetected or suboptimally reported by TBCCD.

The gender gap is a significant concern facing the software industry as the development becomes more geographically distributed. Widely shared reports indicate that gender differences may be specific to each region. However, how complete can these reports be with little to no research reflective of the Open Source Software (OSS) process and communities software is now commonly developed in? Our study presents a multi-region geographical analysis of gender inclusion on GitHub. This mixed-methods approach includes quantitatively investigating differences in gender inclusion in projects across geographic regions and investigate these trends over time using data from contributions to 21,456 project repositories. We also qualitatively understand the unique experiences of developers contributing to these projects through a survey that is strategically targeted to developers in various regions worldwide. Our findings indicate that gender diversity is low across all parts of the world, with no substantial difference across regions. However, there has been statistically significant improvement in diversity worldwide since 2014, with certain regions such as Africa improving at faster pace. We also find that most motivations and barriers to contributions (e.g., lack of resources to contribute and poor working environment) were shared across regions, however, some insightful differences, such as how to make projects more inclusive, did arise. From these findings, we derive and present implications for tools that can foster inclusion in open source software communities and empower contributions from everyone, everywhere.

Developers may choose to implement a library despite the existence of similar libraries, considering factors such as computational performance, language or platform dependency, accuracy, convenience, and completeness of an API. As a result, GitHub hosts several library projects that have overlaps in their functionalities. These overlaps have been of interest to developers from the perspective of code reuse or the preference of one implementation over the other. Through an empirical study, we explore the extent and nature of existence of these similarities in the library functions. We have further studied whether the similarity of functions across different libraries and their associated test suites can be leveraged to reveal defects in one another. We see scope for effectively using the mining of test suites from the perspective of revealing defects in a program or its documentation. Another noteworthy observation made in the study is that similar functions may exist across libraries implemented in the same language as well as in different languages. Identifying the challenges that lie in building a testing tool, we automate the entire process inMetallicus, a test mining and recommendation tool.Metallicusreturns a test suite for the given input of a query function and a template for its test suite. On a dataset of query functions taken from libraries implemented in Java or Python,Metallicusrevealed 46 defects.

A software system evolves over time due to factors such as bug-fixes, enhancements, optimizations and deprecation. As entities interact in a software repository, the alterations made at one point may require the changes to be reflected at various other points to maintain consistency. However, often less attention is given to making appropriate changes to the documentation associated with the functions. Inconsistent documentation is undesirable, since documentation serves as a useful source of information about the functionality. This paper presents a study on the prevalence of function documentations that are indirectly or implicitly dependent on entities other than the associated function. We observe a substantial presence of such documentations, with 62% of the studied Javadoc comments being dependent on other entities, as studied in 11 open-source repositories implemented in Java. We comprehensively analyze the nature of documentation updates made in 1288 commit logs and study patterns to reason about the cause of dependency in the documentation. Our findings from the observed patterns may be applied to suggest documentations that should be updated on making a change in the repository.

Multi-threaded libraries, including the ones advertised as thread-safe, may contain concurrency bugs, and worse, may not include relevant test cases that can drive the program execution towards bug-prone interleavings. Also, the effectiveness of dynamic verification, a prominent concurrency bug detection technique, depends critically on the availability of relevant test cases. Generating such test cases automatically to assist dynamic verification is, therefore, a significant problem.Among hard-to-detect concurrency bugs in multi-threaded Java libraries are communication deadlocks, which occur due to the incorrect usage of wait() and notify() communication primitives. In this work, we present a novel technique to systematically synthesize multi-threaded test cases to expose communication deadlocks. We model these deadlocks as global constraints over the events of two sequential program traces of the library APIs. The task of predicting the relevance of combining two sequential program traces is delegated to an SMT solver. We implement our technique in a prototype tool named REVELIO, and evaluate it on fifteen classes of popular multi-threaded Java libraries. We find that REVELIO is able to synthesize precise tests exposing communication deadlocks, which the state-of-the-art tools cannot.

Static program analysis tools are often required to work with only a small part of a program's source code, either due to the unavailability of the entire program or the lack of need to analyze the complete code. This makes it challenging to use static analysis tools that require a complete and typed intermediate representation (IR). We present JCoffee, a tool that leverages compiler feedback to convert partial Java programs into their compilable counterparts by simulating the presence of missing surrounding code. It works with any well-typed code snippet (class, function, or even an unenclosed group of statements) while making minimal changes to the input code fragment. A demo of the tool is available here: https://youtu.be/O4h2gn2Qls.

The success of dynamic verification techniques for confirming the absence of bugs in concurrent programs rests on their ability to systematically address the interleaving space arising because of the nondeterminism. However, existing dynamic verification engines suffer from the problem of scalability due to the size of the reachable state space that grows exponentially as the number of parallel entities increases. The second front on which the dynamic verification technique struggles is the dependence on the test cases to drive the program, thus being as efficient as the quality of the test cases. Lastly, any verification technique suffers from the lack of a significant benchmark of bugs to prove its worth. This work tries to improve the area of dynamic verification concerning the limitations as mentioned above. We utilize the worthiness and popularity of constraint solvers and establish our work in the realm of concurrent programs.

Developers may choose to implement a library, despite the existence of similar libraries, considering factors such as computational performance, language or platform dependency, and accuracy. As a result, GitHub is a host to several library projects that have overlaps in the functionalities. These overlaps have been of interest to developers from the perspective of code reuse or preferring one implementation over the other. We present an empirical study to explore the extent and nature of existence of these similarities in the library functions. We have further studied whether the similarity among functions across different libraries and their associated test suites can be leveraged to reveal defects in one another. Applying a natural language processing based approach on the documentations associated with functions, we have extracted matching functions across 12 libraries, available on GitHub, over 2 programming languages and 3 themes. Our empirical evaluation indicates existence of a significant number of similar functions across libraries in same as well as different programming languages where a language can influence the extent of existence of similarities. The test suites from another library can serve as an effective source of defect revealing tests. The study resulted in revealing 72 defects in 12 libraries. Further, we analyzed the source of origination of the defect revealing tests. We deduce that issue reports and pull requests can be beneficial in attaining quality test cases not only to test the libraries in which these issues are reported but also for other libraries that are similar in theme.

Automated testing techniques are often assessed on coverage based metrics. However, despite giving good coverage, the test cases may miss the gap between functional specification and the code implementation. This gap may be subtle in nature, arising due to the absence of logical checks, either in the implementation or in the specification, resulting in inconsistencies in the input definition. The inconsistencies may be prevalent especially for structured inputs, commonly specified using string-based data types. Our study on defects reported over popular libraries reveals that such gaps may not be limited to input validation checks. We propose a test generation technique for structured string inputs where we infer inconsistencies in input definition to expose semantic gaps in the method under test and the method specification. We assess this technique using our tool SEGATE, Semantic Gap Tester. SEGATE uses static analysis and automaton modeling to infer the gap and generate test cases. On our benchmark dataset, comprising of defects reported in 15 popular open-source libraries, written in Java, SEGATE was able to generate tests to expose 80% of the defects.

Developers often ask for libraries that implement specific mathematical expressions. A fundamental bottleneck in building information retrieval (IR) systems to answer such mathematical queries is the inability to detect a given expression in software binaries. While we have a few math IR solutions such as EgoMath2 and Tangent-3 that work over text documents, none exist to search over software binaries. Our vision is to build a search system for binaries to answer queries containing mathematical expressions. A wide variety of compilers and differences in the way they optimize the code, pose difficult challenges to solve this problem. In this work, we discuss our preliminary results in detecting mathematical expressions in software binaries. We use a knowledge base assisted approach to solve this problem. We are able to search mathematical expressions with a precision of 80% and a recall of 53%. This work opens up interesting research opportunities in areas such as software security and performance, to help analysts in identifying and analyzing binaries for implementations of mathematical expressions.

Code search with natural language terms performs poorly because programming concepts do not always lexically match their syntactic forms. For example, in Java, the programming concept "array" does not match with its syntactic representation of "[ ]". Code search engines can assist developers more effectively over natural language queries if such mappings existed for a variety of programming languages. In this work, we present a programming language agnostic technique to discover such mappings between syntactic forms and natural language terms representing programming concepts. We use the questions and answers in Stack Overflow to create this mapping. We implement our approach in a tool called ANNE. To evaluate its effectiveness, we conduct a user study in an academic setting in which teaching assistants use ANNE to search for code snippets in student submissions. With the use of ANNE, we find that the participants are 29% quicker with no significant drop in correctness and completeness.

A large number of web applications are written using server-side scripting languages. Although web browsers allow clients to run these applications, it is often cumbersome to depend on desktops for the services provided by the applications. Given the popularity and convenience of mobile devices, there is a clear need to have native mobile apps driving the applications along with web browsers. In this paper, we present a solution to re-engineer web applications developed using server-side scripting languages, into native mobile apps. The solution takes source code of the web application along with its test suite as input and produces corresponding cross-platform mobile apps. The entire re-engineering process is fully automatic requiring no manual intervention at any stage. Our solution is generic enough not only to handle popular server-side scripting languages, but also to output mobile apps that support diverse popular platforms including Android, iOS, and Windows Mobile. To showcase the capability and generality of our solution, we have developed a prototype tool KIRKE to handle applications developed using JSP, PHP, and ASP.NET. We present three case studies based on real-life codebases to evaluate the correctness, coverage, usability, and performance of our solution. The results indicate that KIRKE is capable of generating a mobile app that preserves the functionality of original web application and uses resources more efficiently when compared to the web application running on a mobile browser.

Real-time systems are becoming more complex and open, thus increasing their development and verification costs. Although several static verification tools have been proposed over the last decades, they suffer from scalability and precision problems. As a result, the tools fail to cover all the necessary safety properties for realistic real-time applications involving a large number of components and tasks. Runtime verification (RV) is a formal technique that verifies properties during system execution with the support of monitors. The monitors are generated from formal languages using correct-by-construction generation methods. In this paper, we propose REVERT, a framework developed with a focus on the verification of functional and non-functional properties with timing constraints. The contribution of this work is twofold: (i) a domain-specific specification language allowing the definition of requirements for real-time applications; (ii) a novel mechanism to generate monitors, with state-space and time guarantees, capable of identifying and reacting to timing properties defined with the proposed specification language.

Software evolution in third-party libraries across version upgrades can result in addition of new functionalities or change in existing APIs. As a result, there is a real danger of impairment of backward compatibility. Application developers, therefore, must keep constant vigil over library enhancements to ensure application consistency, i.e., application retains its semantic behavior across library upgrades. In this paper, we present the design and implementation of POLLUX, a framework to detect application-affecting changes across two versions of the same dependent non-adversarial library binary, and provide feedback on whether the application developer should link to the newer version or not. POLLUX leverages relevant application test cases to drive execution through both versions of the concerned library binary, records all concrete effects on the environment, and compares them to determine semantic similarity across the same API invocation for the two library versions. Our evaluation with 16 popular, open-source library binaries shows that POLLUX is accurate with no false positives and works across compiler optimizations.

Software developers rarely write code from scratch. With the existence of Wikipedia, discussion forums, books and blogs, it is hard to imagine a software developer not looking up these sites for sample code while building any non-trivial software system. While researchers have proposed approaches to retrieve relevant posts and code snippets, the need for finding variant implementations of functionally similar code snippets has been ignored. In this work, we propose an approach to automatically create a repository of structurally heterogeneous but functionally similar source code examples from unstructured sources. We evaluate the approach on stackoverflow, a discussion forum that has approximately 19 million posts. The results of our evaluation indicates that the approach extracts structurally different snippets with a precision of 83%. A repository of such heterogeneous source code examples will be useful to programmers in learning different implementation strategies and for researchers working on problems such as program comprehension, semantic clones and code search.

Software is susceptible to malformed data originating from untrusted sources. Occasionally the programming logic or constructs used are inappropriate to handle the varied constraints imposed by legal and well-formed data. Consequently, softwares may produce unexpected results or even crash. In this paper, we present CLOTHO, a novel hybrid approach that saves such softwares from crashing when failures originate from malformed strings or inappropriate handling of strings. CLOTHO statically analyses a program to identify statements that are vulnerable to failures related to associated string data. CLOTHO then generates patches that are likely to satisfy constraints on the data, and in case of failures produces program behavior which would be close to the expected. The precision of the patches is improved with the help of a dynamic analysis. We have implemented CLOTHO for the JAVA String API, and our evaluation based on several popular open-source libraries shows that CLOTHO generates patches that are semantically similar to the patches generated by the programmers in the later versions. Additionally, these patches are activated only when a failure is detected, and thus CLOTHO incurs no runtime overhead during normal execution, and negligible overhead in case of failures.

Runtime monitoring has proven effective in detecting property violations, but it can incur high overhead when monitoring just a single property - particularly when the property relates multiple objects. In practice developers will likely monitor multiple properties in the same execution which will lead to even higher overhead.

Modern robotics systems rely on distributed event-based frameworks to facilitate the assembly of software out of collections of reusable components. These frameworks express component dependencies in data that encode event publish-subscribe relations. This loosely coupled architecture makes it difficult for developers to understand the dependencies and to predict the impacts of a change to a component as the components grow in number and complexity. Moreover, this encoding of dependencies renders traditional techniques for analyzing component dependencies inapplicable, because the dependencies are bound by communication channels rather than data. In this work, we present a program analysis technique that automatically extracts a model of component dependencies from distributed system source code. This model identifies not only the temporal dependencies among components, but also the conditions under which those dependencies are realized. We have implemented the analysis and applied it to systems developed in ROS. The resulting models are succinct and precise, which suggests that programmers will find them comprehensible, and they can be used to document important global dependencies in a system, to compare different versions to identify the impacts of component changes, and to help locate errors.

There has been significant interest in equipping programs with runtime checks aimed at detecting errors to improve fault detection during testing and in the field. Recent work in this area has studied methods for efficiently monitoring a program execution's conformance to path property specifications, e.g., such as those captured by a finite state automaton. These techniques show great promise, but their broad applicability is hampered by the fact that for certain combinations of programs and properties the overhead of checking can slow the program down by up to 3500%.

Model checkers search the space of possible program behaviors to detect errors and to demonstrate their absence. Despite major advances in reduction and optimization techniques, state-space search can still become cost-prohibitive as program size and complexity increase. In this paper, we present a technique for dramatically improving the cost- effectiveness of state-space search techniques for error detection using parallelism. Our approach can be composed with all of the reduction and optimization techniques we are aware of to amplify their benefits. It was developed based on insights gained from performing a large empirical study of the cost-effectiveness of randomization techniques in state-space analysis. We explain those insights and our technique, and then show through a focused empirical study that our technique speeds up analysis by factors ranging from 2 to over 1000 as compared to traditional modes of state-space search, and does so with relatively small numbers of parallel processors.

Programmers using complex libraries and frameworks are faced with the difficult task of ensuring that their implementations comply with complex and informally described rules for proper sequencing of API calls. Recent advances in static and dynamic techniques for checking explicit specifications of program typestate properties have shown promise in addressing this challenge. Unfortunately, static typestate analyses are limited in their scalability and dynamic analyses can suffer from significant run-time overhead. In this paper, we present an approach that exploits information calculated by flow-sensitive static typestate analyses to reformulate the original analysis problem as a residual dynamic typestate analysis. We demonstrate that residual analyses retain the error reporting of unoptimized dynamic analysis while offering the potential for significantly reducing analysis cost