ATOS: Adaptive Program Tracing With Online Control Flow Graph Support

He Sun, Chao Zhang, He Li, Zhenhua Wu, Lifa Wu, Yun LiIEEE Access 2019 · OpenReview

Abstract

Program tracing solutions (i.e., tracers) can faithfully record runtime information about a program's execution and enable flexible and powerful offline analysis. Therefore, they have become fundamental techniques extensively utilized in software analysis applications. However, few tracers have paid attention to the size of traces and corresponding overheads introduced to offline analysis, as well as the Control Flow Graph (CFG) support. This paper presents ATOS, an efficient tracing solution, to address these issues. It adaptively adjusts the granularity of tracing while conservatively preserving the essential execution information. We implement a prototype of ATOS and evaluate it on several benchmarks. The results show that ATOS can greatly reduce the size of a trace and accelerate offline analysis, while preserving the execution states and supporting existing applications seamlessly. For example, using ATOS, the trace produced by the application CryptoHunt is reduced by 46 times, while the analysis time is reduced by 34 times.

Introduction: The Tracing Bottleneck

Program tracing—recording the step-by-step execution of software—is a cornerstone of security research, used for everything from malware analysis to vulnerability discovery. However, traditional tracing faces two massive bottlenecks: the "Data Deluge" and the "CFG Gap."

Traces are often gargantuan; a single execution can generate gigabytes of logs, making offline analysis painfully slow. For instance, the tool CryptoHunt can take over 40 minutes just to parse a single trace of an RSA application. Furthermore, most tracers record raw instruction streams without understanding the program's structure (the Control Flow Graph). Recovering this "map" offline is computationally expensive and is often stymied by self-modifying code or packed malware that hides its true logic.

The general workflow of tracing-based applications, highlighting the bottleneck in parsing and analysis.

Methodology: Adaptive Tracing with ATOS

The authors introduce ATOS (Adaptive Program Tracing), which moves the intelligence of trace analysis from the offline phase to the runtime phase. ATOS maintains an online, augmented version of the program's map called a Shadow CFG. This graph tracks the tracing status of every basic block and function, monitoring memory writes to detect when a program generates new code at runtime.

Adaptive Granularity

Instead of recording every single instruction, ATOS dynamically switches between four levels of detail based on the execution state:

  • Instruction-level: The most detailed; used for new or modified code.
  • Branch-level: Records only which paths are taken at decision points.
  • Function-level (API): Skips internal details of well-known library calls, recording only arguments and return values.
  • Loop-level: Identifies repetitive loops and "folds" them, recording the loop body once and then simply counting iterations.

Check Points (CPs)

To manage these transitions, ATOS instruments the target program with seven types of "check points." These act like smart breakpoints that tell the tracer when to zoom in (e.g., when hitting unrecorded code) or zoom out (e.g., when entering a known loop).

The workflow of ATOS, showing how check points and the Shadow CFG drive adaptive tracing.

Key Insights

The fundamental insight of ATOS is that if a CFG is verified, recording every instruction in a basic block is redundant. If the block was entered and the exit branch is known, the instructions in between are deterministic and can be reconstructed offline.

Loop folding is another essential component. Loops are the primary cause of oversized traces. By identifying loop structures at runtime, ATOS can compress thousands of iterations into a single record. For functions with extremely high "cyclomatic complexity," ATOS uses a "loosen solution," randomly dropping some simple cycles to keep runtime overhead low while still providing a representative trace.

Evaluation and Results

The researchers evaluated ATOS using standard algorithms (OpenSSL, SPEC CPU2000), malware/packers (UPX, ASPack), and real-world APT samples. Comparisons were made against baselines like CryptoHunt, IDA tracer, Intel PT, and Panda.

Key results include:

  • Massive Compression: For the CryptoHunt application, ATOS reduced the trace log size by 46x.
  • Faster Analysis: The time required for post-trace analysis was reduced by 34x on average.
  • Efficiency: Despite the overhead of maintaining a CFG at runtime, ATOS generally outperformed standard tracers by significantly reducing I/O time.
  • Malware De-obfuscation: ATOS successfully identified hidden code layers in packed malware that standard static analysis tools like IDA Pro could not resolve.

Conclusion and Future Work

ATOS demonstrates that adaptive tracing with online CFG support can dramatically improve the efficiency of software analysis. While the current prototype has limitations in multi-threaded environments and potential susceptibility to anti-analysis techniques, future work aims to integrate hardware-assisted tracing (like Intel PT) to further minimize performance penalties.

Summary updated

Abstract

Program tracing solutions (i.e., tracers) can faithfully record runtime information about a program's execution and enable flexible and powerful offline analysis. Therefore, they have become fundamental techniques extensively utilized in software analysis applications. However, few tracers have paid attention to the size of traces and corresponding overheads introduced to offline analysis, as well as the Control Flow Graph (CFG) support. This paper presents ATOS, an efficient tracing solution, to address these issues. It adaptively adjusts the granularity of tracing while conservatively preserving the essential execution information. We implement a prototype of ATOS and evaluate it on several benchmarks. The results show that ATOS can greatly reduce the size of a trace and accelerate offline analysis, while preserving the execution states and supporting existing applications seamlessly. For example, using ATOS, the trace produced by the application CryptoHunt is reduced by 46 times, while the analysis time is reduced by 34 times.
BibTeX
@inproceedings{sun2019atos,
  author = {He Sun and Chao Zhang and He Li and Zhenhua Wu and Lifa Wu and Yun Li},
  title = {{ATOS: Adaptive Program Tracing With Online Control Flow Graph Support}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=cVpSmFxR5G},
}

Loading related content...

Figure