David Zhao

Super-instructions are a crucial optimization method for interpreters, as they combine multiple basic instructions into single specialized operations. The optimization technique reduces dispatch overhead and enables further optimizations in the synthesized operation code for a super-instruction. However, due to combinatorial explosion, identifying super-instructions is a complex selection problem. This paper presents a novel approach for the automated synthesis of super-instruct­ions using a combination of offline dictionary-based compression algorithms and greedy heuristics. Our method addresses the common issue of overlap between super-instructions, which previous approaches often overlook. Additionally, we introduce a meta-compiler for the Ethereum Virtual Machine (EVM) that automatically generates a new interpreter incorporating the super-instructions. The super-instructions generated with our approach result in an 8.45% speedup for the interpreter component of the EVM.

Datalog is becoming increasingly popular as a standard tool for a variety of use cases. Modern Datalog engines can achieve high performance by specializing data structures for relational operations. For example, the Datalog engine Soufflé achieves high performance with a synthesizer that specializes data structures for relations. However, the synthesizer cannot always be deployed, and a fast interpreter is required. This work introduces the design and implementation of the Soufflé Tree Interpreter (STI). Key for the performance of the STI is the support for fast operations on relations. We obtain fast operations by de-specializing data structures so that they can work in a virtual execution environment. Our new interpreter achieves a competitive performance slowdown between 1.32 and 5.67× when compared to synthesized code. If compile time overheads of the synthesizer are also considered, the interpreter can be 6.46× faster on average for the first run.

The popularity of the PDF format and the rich JavaScript environment that PDF viewers offer make PDF documents an attractive attack vector for malware developers. PDF documents present a serious threat to the security of organizations because most users are unsuspecting of them and thus likely to open documents from untrusted sources. We propose to identify malicious PDFs by using conservative abstract interpretation to statically reason about the behavior of the embedded JavaScript code. Currently, state-of-the-art tools either: (1) statically identify PDF malware based on structural similarity to known malicious samples; or (2) dynamically execute the code to detect malicious behavior. These two approaches are subject to evasion attacks that mimic the structure of benign documents or do not exhibit their malicious behavior when being analyzed dynamically. In contrast, abstract interpretation is oblivious to both types of evasions. A comparison with two state-of-the-art PDF malware detection tools shows that our conservative abstract interpretation approach achieves similar accuracy, while being more resilient to evasion attacks.