WebAssembly (Wasm) programs may trigger bugs in their engine implementations. To aid debugging, program reduction techniques try to produce a smaller variant of the input program that still triggers the bug. However, existing execution-unaware program reduction techniques struggle with large and complex Wasm programs, because they rely on static information and apply syntactic transformations, while ignoring the valuable information offered by the input program’s execution behavior. We present RR-Reduce and Hybrid-Reduce, novel execution-aware program reduction techniques that leverage execution behaviors via record and replay. RR-Reduce identifies a bug-triggering function as the target function, isolates that function from the rest of the program, and generates a reduced program that replays only the interactions between the target function and the rest of the program. Hybrid-Reduce combines a complementary execution-unaware reduction technique with RR-Reduce to further reduce program size. We evaluate RR-Reduce and Hybrid-Reduce on 28 Wasm programs that trigger a diverse set of bugs in three engines. On average, RR-Reduce reduces the programs to 1.20% of their original size in 14.5 minutes, which outperforms the state of the art by 33.15× in terms of reduction time. Hybrid-Reduce reduces the programs to 0.13% of their original size in 3.5 hours, which outperforms the state of the art by 3.42× in terms of reduced program size and 2.26× in terms of reduction time. We envision RR-Reduce as the go-to tool for rapid, on-demand debugging in minutes, and Hybrid-Reduce for scenarios where developers require the smallest possible programs.

Translating C to Rust is a promising way to enhance the reliability of legacy system programs. Although the industry has developed an automatic C-to-Rust translator, C2Rust, its translation remains unsatisfactory. One major reason is that C2Rust retains C standard library (libc) function calls instead of replacing them with functions from the Rust standard library (Rust std). However, little work has been done on replacing library functions in C2Rust-generated code. In this work, we focus on replacing the I/O API, an important subset of library functions. This poses challenges due to the semantically different designs of I/O APIs in libc and Rust std. First, the two APIs offer different sets of types that represent the origins (e.g., standard input, files) and capabilities (e.g., read, write) of streams used for I/O. Second, they use different error-checking mechanisms: libc uses internal indicators, while Rust std uses return values. To address these challenges, we propose two static analysis techniques, origin and capability analysis and error source analysis, and use their results to replace the I/O API. Our evaluation shows that the proposed approach is (1) correct, with all 32 programs that have test suites passing the tests after transformation, (2) efficient, analyzing and transforming 422k LOC in 14 seconds, and (3) widely applicable, replacing 82% of I/O API calls.

Quantum software stacks (QSSs), which provide quantum circuit transformers and simulators, enable circuit transformations and the execution of circuits on classical computers. Despite their importance, they have not been effectively tested yet, leaving the correctness in question. The main obstacle to testing is the absence of a testing oracle, which checks the semantics-preservation of circuit transformations and the correctness of simulation results. While previous studies have employed differential and metamorphic testing to circumvent the necessity for an oracle, they have detected very few non-crash bugs. In this work, we address this gap by introducing QASMInfer, an exact inference system for quantum circuits, which computes the probability distribution of possible circuit outcomes. By supporting circuits written in OpenQASM, the de facto standard quantum assembly language used by most QSSs, QASMInfer acts as a unified testing oracle for multiple QSSs. Our design of QASMInfer achieves three key goals: (1) support for dynamic circuits, an important class of quantum circuits, (2) efficiency, and (3) reliability. For efficiency, we introduce two optimizations and an efficient matrix representation. For reliability, we prove physical consistency, ensuring that QASMInfer’s inference results adhere to the physical principles of quantum computing. To simplify the proof, we introduce OpenQASMCore, a core language for OpenQASM, and perform exact inference for OpenQASM by desugaring it to OpenQASMCore. Our implementation and proof are fully mechanized in the Coq proof assistant. Testing six real-world QSSs using QASMInfer revealed 31 bugs, including 20 non-crash bugs, demonstrating QASMInfer’s effectiveness as a testing oracle.

WebAssembly (Wasm) is a low-level binary instruction format designed for safe and high-performance execution across diverse computing environments and runtimes. As Wasm evolves with new features and proposals, testing the correctness and conformance of Wasm runtimes has become increasingly complex. Manually constructing test suites is labor-intensive and difficult to scale, especially as the specification grows in complexity. While fuzzing-based approaches offer partial automation, they often lack a principled connection to the formal specification, and adapting to evolving or restricted subsets of the specification typically requires manual intervention.In this paper, we present WEST, a specification-based test generation framework that automatically produces Wasm test cases from mechanized specifications written in SpecTec, a Wasm-specific specification language. Given any full or subset variant of the Wasm specification as input, WEST aims to systematically generate test programs that conform to the input grammar and validation rules, and capture the runtime behavior defined by its execution semantics. The framework allows flexible integration of different test generation strategies. For instance, we demonstrate both top-down and bottom-up approaches for generating Wasm modules, but the architecture is compatible with other generation techniques as well. The framework enables the creation of customized test cases for engines that support only subsets of the Wasm specification. We evaluate WEST across multiple specification variants and engine configurations, demonstrating that it produces valid and diverse test cases. As a result, it reveals 16 bugs across four Wasm engine implementations, 11 of which are confirmed and fixed. We believe that this work provides a solid foundation for future specification-driven test generation.

Abstract Rust, a modern system programming language, introduces new types that prevent memory bugs and data races. This makes translating legacy system programs from C to Rust a promising approach to enhance their reliability. Since manual code translation is time-consuming, it is desirable to automate the translation. To yield satisfactory results, the translator should have the ability to perform type migration, i.e., removing C types and introducing Rust types in the code. In this work, we aim to automatically port an entire C program to Rust by translating each C function to a Rust function with a signature containing proper Rust types through type migration. This goal is challenging because (1) type migration cannot be achieved through syntactic mappings between type names, and (2) after type migration, function bodies should be correctly restructured based on the precise understanding of the functions’ behavior. To address these difficulties, we leverage large language models (LLMs), which possess knowledge of program semantics and programming idioms. However, naïvely instructing LLMs to translate each function produces unsatisfactory Rust code, containing unmigrated or improperly migrated types and a huge number of type errors. To resolve these issues, we propose three techniques: (1) generating candidate signatures, (2) providing translated callees’ signatures to LLMs, and (3) iteratively fixing type errors using compiler feedback. Our evaluation shows that the proposed approach yields a 63.5% increase in migrated types and a 71.5% decrease in type errors compared to the baseline (the naïve LLM-based translation) with modest performance overhead.

Binary lifting is a key component in binary analysis tools. In order to guarantee the correctness of binary lifting, researchers have proposed various formally verified lifters. However, such formally verified lifters have too strict requirements on binary, which do not sufficiently reflect real-world lifters. In addition, real-world lifters use heuristic-based assumptions to lift binary code, which makes it difficult to guarantee the correctness of the lifted code using formal methods. In this paper, we propose a new interpretation of the correctness of real-world binary lifting. We formalize the process of binary lifting with heuristic-based assumptions used in real-world lifters by dividing it into a series of transformations, where each transformation represents a lift with new abstraction features. We define the correctness of each transformation as filtered-simulation , which is a variant of bi-simulation, between programs before and after transformation. We present three essential transformations in binary lifting and formalize them: (1) control flow graph reconstruction, (2) abstract stack reconstruction, and (3) function input/output identification. We implement our approach for x86-64 Linux binaries, named fible , and demonstrate that it can correctly lift Coreutils and CGC datasets compiled with GCC.

Automatic C-to-Rust translation is a promising way to enhance the reliability of legacy system software. However, C2Rust, an industrially developed translator, generates Rust code with unsafe features, undermining the translation's objective. While researchers have proposed techniques to remove unsafe features in C2Rust-generated code, these efforts have targeted only a limited subset of unsafe features. One important unsafe feature remaining unaddressed is a union, a type consisting of multiple fields sharing the same memory storage. Programmers often place a union with a tag in a struct to record the last-written field, but they can still access wrong fields. In contrast, Rust's tagged unions combine tags and unions at the language level, ensuring correct value access. In this work, we propose techniques to replace unions with tagged unions during C-to-Rust translation. We develop a static analysis that facilitates such replacement by identifying tag fields and the corresponding tag values. The analysis involves a must-points-to analysis computing struct field values and a heuristic interpreting these results. To enhance efficiency, we adopt intraprocedural function-wise analysis, allowing selective analysis of functions. Our evaluation on 36 real-world C programs shows that the proposed approach is (1) precise, identifying 74 tag fields with no false positives and only five false negatives, (2) mostly correct, with 17 out of 23 programs passing tests post-transformation, and (3) efficient, capable of analyzing and transforming 141k LOC in 4,910 seconds.

WebAssembly (Wasm for short) brings a new, powerful capability to the web as well as Edge, IoT, and embedded systems. Wasm is a portable, compact binary code format with high performance and robust sandboxing properties. As Wasm applications grow in size and importance, the complex performance characteristics of diverse Wasm engines demand robust, representative benchmarks for proper tuning. Stopgap benchmark suites, such as PolyBenchC and libsodium, continue to be used in the literature, though they are known to be unrepresentative. Porting of more complex suites remains difficult because Wasm lacks many system APIs and extracting real-world Wasm benchmarks from the web is difficult due to complex host interactions. To address this challenge, we introduce Wasm-R3 , the first record and replay technique for Wasm. Wasm-R3 transparently injects instrumentation into Wasm modules to record an execution trace from inside the module, then reduces the execution trace via several optimizations, and finally produces a replay module that is executable standalone without any host environment—on any engine. The benchmarks created by our approach are (i) realistic, because the approach records real-world web applications, (ii) faithful to the original execution, because the replay benchmark includes the unmodified original code, only adding emulation of host interactions, and (iii) standalone, because the replay benchmarks run on any engine. Applying Wasm-R3 to web-based Wasm applications in the wild demonstrates the correctness of our approach as well as the effectiveness of our optimizations, which reduce the recorded traces by 99.53% and the size of the replay benchmark by 9.98%. We release the resulting benchmark suite of 27 applications, called Wasm-R3-Bench , to the community, to inspire a new generation of realistic and standalone Wasm benchmarks.

Translating legacy system programs from C to Rust is a promising way to enhance their reliability. To alleviate the burden of manual translation, automatic C-to-Rust translation is desirable. However, existing translators fail to generate Rust code fully utilizing Rust’s language features, including algebraic data types. In this work, we focus on tuples and Option/Result types, an important subset of algebraic data types. They are used as functions’ return types to represent those returning multiple values and those that may fail. Due to the absence of these types, C programs use output parameters , i.e., pointer-type parameters for producing outputs, to implement such functions. As output parameters make code less readable and more error-prone, their use is discouraged in Rust. To address this problem, this paper presents a technique for removing output parameters during C-to-Rust translation. This involves three steps: (1) syntactically translating C code to Rust using an existing translator; (2) analyzing the Rust code to extract information related to output parameters; and (3) transforming the Rust code using the analysis result. The second step poses several challenges, including the identification and classification of output parameters. To overcome these challenges, we propose a static analysis based on abstract interpretation, complemented by the notion of abstract read/write sets , which approximate the sets of read/written pointers, and two sensitivities: write set sensitivity and nullity sensitivity . Our evaluation shows that the proposed technique is (1) scalable, with the analysis and transformation of 190k LOC within 213 seconds, (2) useful, with the detection of 1,670 output parameters across 55 real-world C programs, and (3) mostly correct, with 25 out of 26 programs passing their test suites after the transformation.

WebAssembly (Wasm) is a portable low-level bytecode language and virtual machine that has seen increasing use in a variety of ecosystems. Its specification is unusually rigorous – including a full formal semantics for the language – and every new feature must be specified in this formal semantics, in prose, and in the official reference interpreter before it can be standardized. With the growing size of the language, this manual process with its redundancies has become laborious and error-prone, and in this work, we offer a solution. We present SpecTec, a domain-specific language (DSL) and toolchain that facilitates both the Wasm specification and the generation of artifacts necessary to standardize new features. SpecTec serves as a single source of truth — from a SpecTec definition of the Wasm semantics, we can generate a typeset specification, including formal definitions and prose pseudocode descriptions, and a meta-level interpreter. Further backends for test generation and interactive theorem proving are planned. We evaluate SpecTec’s ability to represent the latest Wasm 2.0 and show that the generated meta-level interpreter passes 100% of the applicable official test suite. We show that SpecTec is highly effective at discovering and preventing errors by detecting historical errors in the specification that have been corrected and ten errors in five proposals ready for inclusion in the next version of Wasm. Our ultimate aim is that SpecTec should be adopted by the Wasm standards community and used to specify future versions of the standard.

Java Native Interface (JNI) allows Java applications to access native libraries, but it is challenging to develop correct JNI programs. By leveraging native code, the JNI enables Java developers to implement efficient applications and reuse code written in other programming languages such as C and C++. The core Java libraries use the JNI to provide system features like graphical user interfaces, and mainstream Java Virtual Machines (JVMs) support the JNI. However, implementing correct JNI programs is not trivial due to the complex interoperation semantics between different programming languages. While JVMs do not validate JNI interoperations by default because of the performance overhead, they provide two methods. First, JVMs report the interoperation failures defined in the JNI specification at runtime. Second, they support a debug option, which validates JNI interoperations, degrading the runtime performance. To the best of our knowledge, literature has not thoroughly studied the quality of JVMs’ methods, even though erroneous JNI interoperations may result in incorrect behaviors. In this paper, we empirically study the behaviors of JVMs on erroneous JNI interoperations. For a systematic study, we proposeJUSTGen, a semi-automatic tool that generates JNI test programs incurring erroneous interoperations from the JNI specification.JUSTGenreceives the JNI specification written in our domain-specific language (DSL) and automatically discovers cases that may lead to runtime errors on interoperations using an SMT solver. It then generates test programs that trigger the behaviors on the erroneous cases. Using the generated tests, we empirically evaluate JVM's failure handling mechanisms and the debug option capabilities on erroneous JNI interoperations. Our experiment results show that there exist erroneous cases in which JVMs do not handle failures or handle them differently from the specification. We also found that the JNI debug option does not validate thousands of erroneous cases, which can cause critical runtime errors such as memory corruption and violation of the Java type system. We reported 18 erroneous cases of which JVMs do not handle failures correctly to their respective vendors. Among them, 16 cases have been resolved.

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.

Concurrent programs suffer from data races. To prevent data races, programmers use locks. However, programs can eliminate data races only when they acquire and release correct locks at correct timing. The lock API of C, in which people have developed a large portion of legacy system programs, does not validate the correct use of locks. On the other hand, Rust, a recently developed system programming language, provides a lock API that guarantees the correct use of locks via type checking. This makes rewriting legacy system programs in Rust a promising way to retrofit safety into them. Unfortunately, manual C-to-Rust translation is extremely laborious due to the discrepancies between their lock APIs. Even the state-of-the-art automatic C-to-Rust translator retains the C lock API, expecting developers to replace them with the Rust lock API. In this work, we propose an automatic tool to replace the C lock API with the Rust lock API. It facilitates C-to-Rust translation of concurrent programs with less human effort than the current practice. Our tool consists of a Rust code transformer that takes a lock summary as an input and a static analyzer that efficiently generates precise lock summaries. We show that the transformer is scalable and widely applicable while preserving the semantics; it transforms 66 KLOC in 2.6 seconds and successfully handles 74% of real-world programs. We also show that the analyzer is scalable and precise; it analyzes 66 KLOC in 4.3 seconds.

The conformance testing of programming language implementations is crucial to support correct and consistent execution environments. Because manually maintaining conformance tests for real-world programming languages is cumbersome and labor-intensive, researchers have presented various ways to make conformance tests effective and efficient. One such approach is to use graph coverage, one of the most widely-used coverage criteria, to generate tests that reach different parts of a mechanized language specification. Since mechanized specifications use functions or inductive definitions to describe the semantics of language features, traditional graph coverage criteria for software work as they are. However, they may not produce high-quality conformance tests because language implementations often have specialized execution paths for different features, even when their semantics descriptions use the same functions. Traditional graph coverage may not distinguish test requirements of such language features, which degrades the quality of conformance testing. Similarly, it may not distinguish test requirements of different parts of the same language feature when their semantics descriptions use the same functions. We present feature-sensitive (FS) coverage as a novel coverage criterion to generate high-quality conformance tests for language implementations. It is a general extension of graph coverage, refining conventional test requirements using the innermost enclosing language features. We also introduce feature-call-path-sensitive (FCPS) coverage, a variant of FS coverage, and extend both coverage criteria using the 𝑘-limiting approach. To evaluate the effectiveness of the new coverage criteria for language implementations, we apply them to a mechanized specification of JavaScript. We extend JEST, the state-of-the-art JavaScript conformance test synthesizer using coverage-guided mutational fuzzing, with various FS and FCPS coverage criteria. For the latest JavaScript language specification (ES13, 2022), our tool automatically synthesizes 237,981 conformance tests in 50 hours with five coverage criteria. We evaluated the conformance of eight mainstream JavaScript implementations (four engines and four transpilers) with the synthesized conformance tests and discovered bugs in all of them. The tool detected 143 distinct conformance bugs (42 in engines and 101 in transpilers), 85 of which were confirmed by the developers and 83 of which were newly discovered bugs.

Summary Declarative static program analysis has become one of the widely‐used program analysis techniques. Declarative static analyzers perform three steps: creating databases of facts from program source code, evaluating rules to generate new facts, and running queries over facts to extract all information related to specific properties via query systems. Declarative static analyzers can easily target diverse programming languages by modifying only databases and rules for new languages. Because query systems are independent of programming languages, they are reusable for new languages. However, even when declarative analyzers support multiple programming languages they do not currently support the analysis of multilingual programs written in two or more programming languages. We propose a systematic methodology that extends a declarative static analyzer supporting multiple languages to support multilingual programs as well. The main idea is to reuse existing components of the analyzer. Our approach first generates a merged database of facts, consisting of multiple logical language spaces. It allows existing language‐specific rules to derive new facts for the corresponding language from the facts in the corresponding language space. Then, it defines language‐interoperation rules that handle the language interoperation semantics. Finally, it uses the same query system to get analysis results leveraging the language interoperation semantics. We develop a proof‐of‐concept declarative static analyzer for multilingual programs by extending CodeQL, which can track dataflows across language boundaries. Our evaluation shows that the analyzer successfully tracks dataflows across Java‐C and Python‐C language boundaries and detects genuine interoperation bugs in real‐world multilingual programs.

JNI programs are widely used thanks to the combined benefits of C and Java programs. However, because understanding the interaction behaviors between two different programming languages is challenging, JNI program development is difficult to get right and vulnerable to security attacks. Thus, researchers have proposed static analysis of JNI program source code to detect bugs and security vulnerabilities in JNI programs. Unfortunately, such source code analysis is not applicable to compiled JNI programs that are not open-sourced or open-source JNI programs containing third-party binary libraries. While JN-SAF, the state-of-the-art analyzer for compiled JNI programs, can analyze binary code, it has several limitations due to its symbolic execution and summary-based bottom-up analysis. In this paper, we propose a novel approach to statically analyze compiled JNI programs without their source code using binary decompilation. Unlike JN-SAF that analyzes binaries directly, our approach decompiles binaries and analyzes JNI programs with the decompiled binaries using an existing JNI program analyzer for source code. To decompile binaries to compilable C source code with precise JNI-interoperation-related types, we improve an existing decompilation tool by leveraging the characteristics of JNI programs. Our evaluation shows that the approach is precise as almost the same as the state-of-the-art JNI program analyzer for source code, and more precise than JN-SAF.

JavaScript is one of the most dominant programming languages. However, despite its popularity, it is a challenging task to correctly understand the behaviors of JavaScript programs because of their highly dynamic nature. Researchers have developed various static analyzers that strive to conform to ECMA-262, the standard specification of JavaScript. Unfortunately, all the existing JavaScript static analyzers require manual updates for new language features. This problem has become more critical since 2015 because the JavaScript language itself rapidly evolves with a yearly release cadence and open development process.

Java Native Interface (JNI) provides a way for Java applications to access native libraries, but it is difficult to develop correct JNI programs. By leveraging native code, the JNI enables Java developers to implement efficient applications and to reuse code written in other programming languages such as C and C++. Besides, the core Java libraries already use the JNI to provide system features like a graphical user interface. As a result, many mainstream Java Virtual Machines (JVMs) support the JNI. However, due to the complex interoperation semantics between different programming languages, implementing correct JNI programs is not trivial. Moreover, because of the performance overhead, JVMs do not validate erroneous JNI interoperations by default, but they validate them only when the debug feature, the -Xcheck:jni option, is enabled. Therefore, the correctness of JNI programs highly relies on the checks by the -Xcheck:jni option of JVMs. Questions remain, however, on the quality of the checks provided by the feature. Are there any properties that the -Xcheck:jni option fails to validate? If so, what potential issues can arise due to the lack of such validation? To the best of our knowledge, no research has explored these questions in-depth. In this paper, we empirically study the validation quality and impacts of the -Xcheck:jni option on mainstream JVMs using unspecified corner cases in the JNI specification. Such unspecified cases may lead to unexpected run-time behaviors because their semantics is not defined in the specification. For a systematic study, we propose JUSTGEN, a semi-automated approach to identify unspecified cases from a specification and generate test programs. JUSTGEN receives the JNI specification written in our domain specific language (DSL), and automatically discovers unspecified cases using an SMT solver. It then generates test programs that trigger the behaviors of unspecified cases. Using the generated tests, we empirically study the validation ability of the -Xcheck:jni option. Our experimental result shows that the JNI debug feature does not validate thousands of unspecified cases on JVMs, and they can cause critical run-time errors such as violation of the Java type system and memory corruption. We reported 792 unspecified cases that are not validated by JVMs to their corresponding JVM vendors. Among them, 563 cases have been fixed and the remaining cases will be fixed in near future. Based on our empirical study, we believe that the JNI specification should specify the semantics of the missing cases clearly and the debug feature should be supported completely.

Modern programming follows the continuous integration (CI) and continuous deployment (CD) approach rather than the traditional waterfall model. Even the development of modern programming languages uses the CI/CD approach to swiftly provide new language features and to adapt to new development environments. Unlike in the conventional approach, in the modern CI/CD approach, a language specification is no more the oracle of the language semantics because both the specification and its implementations (interpreters or compilers) can co-evolve. In this setting, both the specification and implementations may have bugs, and guaranteeing their correctness is non-trivial. In this paper, we propose a novelN+1-versiondifferentialtestingto resolve the problem. Unlike the traditional differential testing, our approach consists of three steps: (1) to automatically synthesize programs guided by the syntax and semantics from a given language specification, (2) to generate conformance tests by injecting assertions to the synthesized programs to check their final program states, (3) to detect bugs in the specification and implementations via executing the conformance tests on multiple implementations and (4) to localize bugs on the specification using statistical information. We actualize our approach for the JavaScript programming language via JEST, which performsN+1-version differential testing for modern JavaScript engines and ECMAScript, the language specification describing the syntax and semantics of JavaScript in a natural language. We evaluated JEST with four JavaScript engines that support all modern JavaScript language features and the latest version of ECMAScript (ES11, 2020). JEST automatically synthesized 1,700 programs that covered 97.78% of syntax and 87.70% of semantics from ES11. Using the assertion-injected JavaScript programs, it detected 44 engine bugs in four different engines and 27 specification bugs in ES11.

JavaScript is one of the mainstream programming languages for client-side programming, server-side programming, and even embedded systems. Various JavaScript engines developed and maintained in diverse fields must conform to the syntax and semantics described in ECMAScript, the standard specification of JavaScript. Since an incorrect description in ECMAScript can lead to wrong JavaScript engine implementations, checking the correctness of ECMAScript is critical and essential. However, all the specification updates are currently manually reviewed by the Ecma Technical Committee 39 (TC39) without any automated tools. Moreover, in late 2014, the committee announced the yearly release cadence and open development process of ECMAScript to quickly adapt to evolving development environments. Because of such frequent updates, checking the correctness of ECMAScript becomes more labor-intensive and error-prone.To alleviate the problem, we propose JSTAR, a JavaScript Specification Type Analyzer using Refinement. It is the first tool that performs type analysis on JavaScript specifications and detects specification bugs using a bug detector. For a given specification, JSTAR first compiles each abstract algorithm written in a structured natural language to a corresponding function in IRES, an untyped intermediate representation for ECMAScript. Then, it performs type analysis for compiled functions with specification types defined in ECMAScript. Based on the result of type analysis, JSTAR detects specification bugs using a bug detector consisting of four checkers. To increase the precision of the type analysis, we present condition-based refinement for type analysis, which prunes out infeasible abstract states using conditions of assertions and branches. We evaluated JSTAR with all 864 versions in the official ECMAScript repository for the recent three years from 2018 to 2021. JSTAR took 137.3 seconds on average to perform type analysis for each version, and detected 157 type-related specification bugs with 59.2% precision; 93 out of 157 bugs are true bugs. Among them, 14 bugs are newly detected by JSTAR, and the committee confirmed them all.

JavaScript has become one of the most widely used programming languages for web development, server-side programming, and even micro-controllers for IoT. However, its extremely functional and dynamic features degrade the performance and precision of static analysis. Moreover, the variety of built-in functions and host environments requires excessive manual modeling of their behaviors. To alleviate these problems, researchers have proposed various ways to leverage dynamic analysis during JavaScript static analysis. However, they do not fully utilize the high performance of dynamic analysis and often sacrifice the soundness of static analysis. In this paper, we present dynamic shortcuts, a new technique to flexibly switch between abstract and concrete execution during JavaScript static analysis in a sound way. It can significantly improve the analysis performance and precision by using highly-optimized commercial JavaScript engines and lessen the modeling efforts for opaque code. We actualize the technique via SAFEDS, an extended combination of SAFE and Jalangi, a static analyzer and a dynamic analyzer, respectively. We evaluated SAFEDS using 269 official tests of Lodash 4 library. Our experiment shows that SAFEDS is 7.81x faster than the baseline static analyzer, and it improves the precision to reduce failed assertions by 12.31% on average for 22 opaque functions.

Ethereum, one of the most popular blockchain platforms, provides financial transactions like payments and auctions through smart contracts. Due to the immense interest in smart contracts in academia, the research community of smart contract security has made a significant improvement recently. Researchers have reported various security vulnerabilities in smart contracts, and developed static analysis tools and verification frameworks to detect them. However, it is unclear whether such great efforts from academia has indeed enhanced the security of smart contracts in reality.

Most programming languages support foreign language interoperation that allows developers to integrate multiple modules implemented in different languages into a single multilingual program. While utilizing various features from multiple languages expands expressivity, differences in language semantics require developers to understand the semantics of multiple languages and their inter-operation. Because current compilers do not support compile-time checking for interoperation, they do not help developers avoid interoperation bugs. Similarly, active research on static analysis and bug detection has been focusing on programs written in a single language.

JavaScript was initially designed for client-side programming in web browsers, but its engine is now embedded in various kinds of host software. Despite the popularity, since the JavaScript semantics is complex especially due to its dynamic nature, understanding and reasoning about JavaScript programs are challenging tasks. Thus, researchers have proposed several attempts to define the formal semantics of JavaScript based on ECMAScript, the official JavaScript specification. However, the existing approaches are manual, labor-intensive, and error-prone and all of their formal semantics target ECMAScript 5.1 (ES5.1, 2011) or its former versions. Therefore, they are not suitable for understanding modern JavaScript language features introduced since ECMAScript 6 (ES6, 2015). Moreover, ECMAScript has been annually updated since ES6, which already made five releases after ES5.1.

Summary Android supports seamless user experience by maintaining activities from different applications (apps) in the same activity stack. Although such close inter‐app communication is essential in the Android framework, the powerful inter‐app communication contains vulnerabilities that can inject malicious activities into a victim app's activity stack to hijack user interaction flows. In this article, we demonstrate activity injection attacks with a simple malware, and formally specify the activity activation mechanism using operational semantics. Based on the operational semantics, we develop a static analysis tool, which analyzes Android apps to detect activity injection attacks. Our tool is fast enough to analyze real‐world Android apps in 6 seconds on average, and our experiments found that 1761 apps out of 129,756 real‐world Android apps inject their activities into other apps' tasks. Moreover, we propose a defense mechanism, dubbed signature‐based activity access control (SAAC), which completely prohibits activity injection attacks. The defense mechanism is general enough to keep the current Android multitasking features intact, and it is simple enough to be independent of the complex activity activation semantics, which does not increase activity activation time noticeably. With the extension of the formal semantics for SAAC, we prove that SAAC correctly mitigates activity injection attacks without any false alarms.

Static program analysis often encounters problems in analyzing library code. Most real-world programs use library functions intensively, and library functions are usually written in different languages. For example, static analysis of JavaScript programs requires analysis of the standard built-in library implemented in host environments. A common approach to analyze such opaque code is for analysis developers to build models that provide the semantics of the code. Models can be built either manually, which is time consuming and error prone, or automatically, which may limit application to different languages or analyzers. In this paper, we present a novel mechanism to support automatic modeling of opaque code, which is applicable to various languages and analyzers. For a given static analysis, our approach automatically computes analysis results of opaque code via dynamic testing during static analysis. By using testing techniques, the mechanism does not guarantee sound over-approximation of program behaviors in general. However, it is fully automatic, is scalable in terms of the size of opaque code, and provides more precise results than conventional over-approximation approaches. Our evaluation shows that although not all functionalities in opaque code can (or should) be modeled automatically using our technique, a large number of JavaScript built-in functions are approximated soundly yet more precisely than existing manual models.

Hybrid applications (apps) have become one of the most attractive options for mobile app developers thanks to its support for portability and device-specific features. Android hybrid apps, for example, support portability via JavaScript, device-specific features via Android Java, and seamless interactions between them. However, their interoperation semantics is often under-documented and unintuitive, which makes hybrid apps vulnerable to errors. While recent research has addressed such vulnerabilities, none of them are based on any formal grounds. In this paper, we present the first formal specification of Android interoperability to establish a firm ground for understanding and reasoning about the interoperations. We identify its semantics via extensive testing and thorough inspection of Android source code. We extend an existing multi-language semantics to formally express the key features of hybrid mechanisms, dynamic and indistinguishable interoperability. Based on the extensions, we incrementally define a formal interoperation semantics and disclose its numerous unintuitive and inconsistent behaviors. Moreover, on top of the formal semantics, we devise a lightweight type system that can detect bugs due to the unintuitive inter-language communication. We show that it detects more bugs more efficiently than HybriDroid, the state-of-the-art analyzer of Android hybrid apps, in real-world Android hybrid apps.

Mobile advertising has become a popular advertising approach by taking advantage of various information from mobile devices and rich interaction with users. Mobile advertising platforms show advertisements of nearby restaurants to users using the geographic locations of their mobile devices, and also allow users to make reservations easily using their phone numbers. However, at the same time, they may open the doors for advertisements to steal device information or to perform malicious behaviors. When application developers integrate mobile advertising platform SDKs (AdSDKs) to their applications, they are informed of only the permissions required by the AdSDKs, and they may not be aware of the rich functionalities of the SDKs that are available to advertisements.

Many object-oriented languages provide method overloading, which allows multiple method declarations with the same name. For a given method invocation, in order to choose what method declaration to invoke, multiple dispatch considers the run-time types of the arguments. While multiple dispatch can support binary methods (such as mathematical operators) intuitively and consistently, it is difficult to guarantee that calls will be neither ambiguous nor undefined at run time, especially in the presence of expressive language features such as multiple inheritance and parametric polymorphism. Previous efforts have formalized languages that include such features by using overloading rules that guarantee a unique and type-sound resolution of each overloaded method call; in many cases, such rules resolve ambiguity by treating the arguments asymmetrically. Here we present the first formal specification of a strongly typed object-oriented language with symmetric multiple dispatch, multiple inheritance, and parametric polymorphism with variance. We define both a static (type- checking) semantics and a dynamic (dispatching) semantics and prove the type soundness of the language, thus demonstrating that our novel dynamic dispatch algorithm is consistent with the static semantics. Details of our dynamic dispatch algorithm address certain technical challenges that arise from structural asymmetries inherent in object-oriented languages (e.g., classes typically declare ancestors explicitly but not descendants).

Summary While JavaScript programs have become pervasive in web applications, they remain hard to reason about. In this context, most static analyses for JavaScript programs require precise call graph information, since the presence of large numbers of spurious callees significantly deteriorates precision. One of the most challenging JavaScript features that complicate the inference of precise static call graph information is read/write accesses to object fields, the names of which are computed at runtime. JavaScript framework libraries often exploit this facility to build objects from other objects, as a way to simulate sophisticated high‐level programming constructions. Such code patterns are difficult to analyze precisely, due to weak updates and limitations of unrolling techniques. In this paper, we observe that precise field origination relations can be inferred by locally reasoning about object copies, both regarding to the object and to the program structure, and we propose an abstraction that allows to separately reason about field read/write access patterns working on different fields and to carefully handle the sets of JavaScript object fields. We formalize and implement an analysis based on this technique. We evaluate the performance and precision of the analysis on the computation of call graph information for examples from jQuery tutorials.

JavaScript web applications (apps) are prevalent these days, and quality assurance of web apps gets even more important. Even though researchers have studied various analysis techniques and software industries have developed code analyzers for their own code repositories, statically analyzing web apps in a sound and scalable manner is challenging. On top of dynamic features of JavaScript, abundant execution flows triggered by user events make a sound static analysis difficult. In this paper, we propose a novel EventHandler ( EH )-based static analysis for web apps using dynamically collected state information. Unlike traditional whole-program analyses, the EH -based analysis intentionally analyzes partial execution flows using concrete user events. Such analyses surely miss execution flows in the entire program, but they analyze less infeasible flows reporting less false positives. Moreover, they can finish analyzing partial flows of web apps that whole-program analyses often fail to finish analyzing, and produce partial bug reports. Our experimental results show that the EH -based analysis improves the precision dramatically compared with a state-of-the-art JavaScript whole-program analyzer, and it can finish analysis of partial execution flows in web apps that the whole-program analyzer fails to analyze within a timeout.

Summary Statically analyzing JavaScript applications often requires an analysis of JavaScript libraries because many JavaScript applications use libraries. However, static analysis techniques for JavaScript are not yet ready for analyzing libraries in ascalableandprecisemanner. Simply loading JavaScript libraries uses various dynamic features of JavaScript, which cause static analyzers to suffer from mutually intermingled problems of scalability and imprecision. In this paper, we present a loop‐sensitive analysis (LSA) technique, which can improve the analysis scalability when analyzing JavaScript libraries by enhancing the analysis precision of loops. The LSA technique distinguishes loop iterations when loop conditions can be determined to be either true or false precisely. We formalize LSA in the abstract interpretation framework in the presence of tricky language features such as exceptions and prove its soundness and precision theorems using Coq. We evaluate our LSA implementation with the analysis results of programs that use 5 JavaScript libraries and show that LSA significantly improves the analysis scalability and precision of an existing JavaScript static analyzer when analyzing JavaScript libraries. In addition, using the configurability of LSA, we experimentally show the correlation between scalability and precision in the analysis of JavaScript libraries. We found that even the analysis of simple programs that just load jQuery, which is the most popular JavaScript library, in a scalable way requires distinguishing not only the last 4 functions being called but also 40 iterations in each loop with 2‐level nested loops at least. Both the mechanization and implementation of LSA are publicly available.

Program analyses often utilize various forms of sensitivity such as context sensitivity, call-site sensitivity, and object sensitivity. These techniques all allow for more precise program analyses, that are able to compute more precise program invariants, and to verify stronger properties. Despite the fact that sensitivity techniques are now part of the standard toolkit of static analyses designers and implementers, no comprehensive frameworks allow the description of all common forms of sensitivity. As a consequence, the soundness proofs of static analysis tools involving sensitivity often rely on ad hoc formalization, which are not always carried out in an abstract interpretation framework. Moreover, this also means that opportunities to identify similarities between analysis techniques to better improve abstractions or to tune static analysis tools can easily be missed. In this article, we present and formalize a framework for the description of sensitivity in static analysis . Our framework is based on a powerful abstract domain construction, and utilizes reduced cardinal power to tie basic abstract predicates to the properties analyses are sensitive to. We formalize this abstraction, and the main abstract operations that are needed to turn it into a generic abstract domain construction. We demonstrate that our approach can allow for a more precise description of program states, and that it can also describe a large set of sensitivity techniques, both when sensitivity criteria are static (known before the analysis) or dynamic (inferred as part of the analysis), and sensitive analysis tuning parameters. Last, we show that sensitivity techniques used in state-of-the-art static analysis tools can be described in our framework.

Android supports seamless user experience by maintaining activities from different apps in the same activity stack. While such close inter-app communication is essential in the Android framework, the powerful inter-app communication contains vulnerabilities that can inject malicious activities into a victim app's activity stack to hijack user interaction flows. In this paper, we demonstrate activity injection attacks with a simple malware, and formally specify the activity activation mechanism using operational semantics. Based on the operational semantics, we develop a static analysis tool, which analyzes Android apps to detect activity injection attacks. Our tool is fast enough to analyze real-world Android apps in 6 seconds on average, and our experiments found that 1,761 apps out of 129,756 real-world Android apps inject their activities into other apps' tasks.

jQuery is the most popular JavaScript library but the state-of-the-art static analyzers for JavaScript applications fail to analyze simple programs that use jQuery. In this paper, we present a novel abstract string domain whose elements are simple regular expressions that can represent prefix, infix, and postfix substrings of a string and even their sets. We formalize the new domain in the abstract interpretation framework with abstract models of strings and objects commonly used in the existing JavaScript analyzers. For practical use of the domain, we present polynomial-time inclusion decision rules between the regular expressions and prove that the rules exactly capture the actual inclusion relation. We have implemented the domain as an extension of the open-source JavaScript analyzer, SAFE, and we show that the extension significantly improves the scalability and precision of the baseline analyzer in analyzing programs that use jQuery.

Analyzing real-world JavaScript web applications is a challenging task. On top of understanding the semantics of JavaScript, it requires modeling of web documents, platform objects, and interactions between them. Not only the JavaScript language itself but also its usage patterns are extremely dynamic. JavaScript can generate code and run it during evaluation, and most web applications load JavaScript code dynamically. Such dynamic characteristics of JavaScript web applications make pure static analysis approaches inapplicable. In this talk, we present our attempts to analyze JavaScript web applications in the wild mostly statically using various approaches. From pure JavaScript programs to JavaScript web applications using platform-specific libraries and dynamic code loading, we explain technical challenges in analyzing each of them and how we built an open-source analysis framework for JavaScript, SAFE, that addresses the challenges incrementally. In spite of active research accomplishments in analysis of JavaScript web applications, many issues still remain to be resolved such as events, callback functions, and hybrid web applications. We discuss possible future research directions and open challenges.

Mobile applications (apps) have long invaded the realm of desktop apps, and hybrid apps become a promising solution for supporting multiple mobile platforms. Providing both platform-specific functionalities via native code like native apps and user interactions via JavaScript code like web apps, hybrid apps help developers build multiple apps for different platforms without much duplicated efforts. However, most hybrid apps are developed in multiple programming languages with different semantics, which may be vulnerable to programmer errors. Moreover, because untrusted JavaScript code may access device-specific features via native code, hybrid apps may be vulnerable to various security attacks. Unfortunately, no existing tools can help hybrid app developers by detecting errors or security holes. In this paper, we present HybriDroid, the first static analysis framework for Android hybrid apps. We investigate the semantics of Android hybrid apps especially for the interoperation mechanism of Android Java and JavaScript. Then, we design and implement a static analysis framework that analyzes inter-communication between Android Java and JavaScript. As example analyses supported by HybriDroid, we implement a bug detector that identifies programmer errors due to the hybrid semantics, and a taint analyzer that finds information leaks cross language boundaries. Our empirical evaluation shows that the tools are practically usable in that they found previously uncovered bugs in real-world Android hybrid apps and possible information leaks via a widely-used advertising platform.

Programming languages grow over time that requires frequent changes in language manipulations such as compilation, interpretation, and analysis. Because the very first step of most language manipulations is parsing, whether parsing can adapt to changes easily, quickly, and correctly, it affects the scalability of language manipulations. Even though various parsing techniques have been well studied theoretically, their practical experiences in scalable frameworks have not been available. In this paper, we present our experiences with parsing in scalable frameworks. We first describe our trials and errors using various parsing techniques in developing parsers for the Fortress programming language. Because Fortress was a scientific language under development, its mathematical and growable syntax introduced new challenges in parsing. We summarize the lessons learned from parsing Fortress, and we share our experience of applying the lessons to parsing the JavaScript programming language. While JavaScript is one of the most widely used languages, JavaScript itself and its diverse variants keep extending its syntax, and the extremely dynamic features of JavaScript also add new challenges in parsing. Using automatic generation tools and methods like staged parsing and automatic extraction and testing of examples in language specifications, our methodology for scalable parsing has shown to be very effective in practice. Copyright © 2015 John Wiley & Sons, Ltd.

In object-oriented programs, objects often provide methods whose parameter types or return types are the object types themselves. For example, the parameter types of binary methods are the types of their receiver objects, and the return types of some factory methods are the types of their enclosing objects. However, most object-oriented languages do not support such methods precisely because their type systems do not support explicit recursive types, which lead to a mismatch between subclassing and subtyping. This mismatch means that an expression of a subclass may not always be usable in a context where an expression of a superclass is expected, which is not intuitive in an object-oriented setting. Researchers have proposed various type-sound approaches to support methods with types of their enclosing object types denoted by some variants of ThisType, but they reject reasonable and useful methods due to unpermissive type systems or they use less precise declared inexact types rather than runtime exact types. In this article, we present a thorough approach to support methods with ThisTypes: from a new encoding of objects in a typed lambda calculus that allows subtyping by subclassing to an open-source implementation as an extension of the Java programming language. We first provide real-world examples that motivate the need for ThisTyped methods to precisely describe desired properties of programs. We define a new object encoding that enables subtyping by subclassing even in the presence of negative occurrences of type recursion variables by distinguishing object types from existential object types. Based on this object encoding, we formalize language features to support ThisTyped methods with a core calculus CoreThisJava, and prove its type soundness. Finally, we provide ThisJava, a prototype implementation of the calculus, to show its backward compatibility, and we make it publicly available. We believe that our approach theoretically expands the long pursuit of an object-oriented language with ThisTypes to support more useful methods with more precise types.

Android devices and applications become prevalent and ask for unanticipated capabilities thanks to the increased interests in smartphones and web applications. As a way to use the capabilities not directly available to ordinary users, applications have used Android Debug Bridge (ADB), a command line tool to communicate with Android devices for debugging purposes. While ADB provides powerful features that require permissions to use critical system resources, it opens a gate to adversaries.

The numbers and sizes of JavaScript applications are ever growing but static analysis techniques for analyzing large-scale JavaScript applications are not yet ready in a scalable and precise manner. Even when building complex software like compilers and operating systems in JavaScript, developers do not get much benefits from existing static analyzers, which suffer from mutually intermingled problems of scalability and imprecision. In this paper, we present Loop-Sensitive Analysis (LSA) that improves the analysis scalability by enhancing the analysis precision in loops. LSA distinguishes loop iterations as many as needed by automatically choosing loop unrolling numbers during analysis. We formalize LSA in the abstract interpretation framework and prove its soundness and precision theorems using Coq. We evaluate our implementation of LSA using the analysis results of main web pages in the 5 most popular websites and those of the programs that use top 5 JavaScript libraries, and show that it outperforms the state-of-the-art JavaScript static analyzers in terms of analysis scalability. Our mechanization and implementation of LSA are both publicly available.

We present a novel approach to analyze large-scale JavaScript applications statically by tuning the analysis scalability possibly giving up its soundness. For a given sound static baseline analysis of JavaScript programs, our framework allows users to define a sound approximation of selected executions that they are interested in analyzing, and it derives a tuned static analysis that can analyze the selected executions practically. The selected executions serve as parameters of the framework by taking trade-off between the scalability and the soundness of derived analyses. We formally describe our framework in abstract interpretation, and implement two instances of the framework. We evaluate them by analyzing large-scale real-world JavaScript applications, and the evaluation results show that the framework indeed empowers users to experiment with different levels of scalability and soundness. Our implementation provides an extra level of scalability by deriving sparse versions of derived analyses, and the implementation is publicly available.

We present SAFEWapp, an open-source static analysis framework for JavaScript web applications. It provides a faithful (partial) model of web application execution environments of various browsers, based on empirical data from the main web pages of the 9,465 most popular websites. A main feature of SAFEWapp is the configurability of DOM tree abstraction levels to allow users to adjust a trade-off between analysis performance and precision depending on their applications. We evaluate SAFEWapp on the 5 most popular JavaScript libraries and the main web pages of the 10 most popular websites in terms of analysis performance, precision, and modeling coverage. Additionally, as an application of SAFEWapp, we build a bug detector for JavaScript web applications that uses static analysis results from SAFEWapp. Our bug detector found previously undiscovered bugs including ones from wikipedia.org and amazon.com.

The evolution of Web 2.0 technologies makes web applications prevalent in various platforms including mobile devices and smart TVs. While one of the driving technologies of web applications is JavaScript, the extremely dynamic features of JavaScript make it very difficult to define and detect errors in JavaScript applications. The problem becomes more important and complicated for JavaScript web applications which may lead to severe security vulnerabilities. To help developers write safe JavaScript web applications using vendor-specific Web APIs, vendors specify their APIs often in Web IDL, which enables both API writers and users to communicate better by understanding the expected behaviors of the Web APIs. In this paper, we present SAFEWAPI, a tool to analyze Web APIs and JavaScript web applications that use the Web APIs and to detect possible misuses of Web APIs by the web applications. Even though the JavaScript language semantics allows to call a function defined with some parameters without any arguments, platform developers may require application writers to provide the exact number of arguments. Because the library functions in Web APIs expose their intended semantics clearly to web application developers unlike pure JavaScript functions, we can detect wrong uses of Web APIs precisely. For representative misuses of Web APIs defined by software quality assurance engineers, our SAFEWAPI detects such misuses in real-world JavaScript web applications.

The with statement in JavaScript makes static analysis of JavaScript applications difficult by introducing a new scope at run time and thus invalidating lexical scoping. Therefore, many static approaches to JavaScript program analysis and the strict mode of ECMAScript 5 simply disallow the with statement. To justify exclusion of the with statement, we should better understand the actual usage patterns of the with statement.

The JavaScript programming language, originally developed as a simple scripting language, is now the language of choice for web applications. All the top 100 sites on the web use JavaScript and its use outside web pages is rapidly growing. However, JavaScript is not yet ready for programming in the large: it does not support a module system. Lack of namespaces introduces module patterns, and makes it difficult to use multiple JavaScript frameworks together.

In previous work, we presented rules for defining overloaded functions that ensure type safety under symmetric multiple dispatch in an object-oriented language with multiple inheritance, and we showed how to check these rules without requiring the entire type hierarchy to be known, thus supporting modularity and extensibility. In this work, we extend these rules to a language that supports parametric polymorphism on both classes and functions.

We present a static analysis that detects potential runtime exceptions that are raised and never handled inside Standard ML (SML) programs. Contrary to our earlier method (Yi, 1994) based on abstract interpretation, where the input program's control flow is simultaneously computed while our exception analysis progresses, we separate the two phases in a manner similar to conventional data flow analysis. Before the exception analysis begins, we first estimate the input program's control flow from the type information from SML/NJ compiler. Based on this call-graph structure, exception flow is specified as a set of equations, whose solution is computed using an iterative least fixpoint method. A prototype of this analysis is applied to two realistic SML programs (ML-LEX and OR-SML core) and is 3 or 40 times faster than the earlier method and saves memory by 35 or 65 percent.