General

Program Analysis Reading List - Rolf Rolles - http://www.msreverseengineering.com/program-analysis-reading-list/
Reading for graduate students in static analysis - http://matt.might.net/articles/books-papers-materials-for-graduate-students/#analysis
Program Analysis Resources - http://reversing.io/resources/
Conferences on Software Verification and Analysis - https://github.com/soarlab/conferences
Static Analysis Roadmap - https://tpiazza.me/posts/2017-11-01-static-analysis-roadmap.html

Symbolic Execution

Awesome Symbolic Execution - https://github.com/ksluckow/awesome-symbolic-execution
Symbolic execution history timeline: https://github.com/enzet/symbolic-execution
Symbolic Execution: Intuition and Implementation - http://www.usrsb.in/symbolic-execution-intuition-and-implementation.html
A bibliography of papers related to symbolic execution - https://github.com/saswatanand/symexbib
A Survey of Symbolic Execution Techniques
- ACM Computing Surveys 51(3) 2018
- Roberto Baldoni, Emilio Coppa, Daniele Cono D'Elia, Camil Demetrescu, Irene Finocchi
- https://github.com/season-lab/survey-symbolic-execution
- https://arxiv.org/abs/1610.00502
All You Ever Wanted to Know About Dynamic Taint Analysis and Forward Symbolic Execution (but might have been afraid to ask)
- Security and Privacy (SP), 2010
- Edward J. Schwartz, Thanassis Avgerinos, David Brumley
- Paper: https://edmcman.github.io/papers/oakland10.pdf
- Slides: https://edmcman.github.io/pres/oakland10.pdf
Systematic Comparison of Symbolic Execution Systems: Intermediate Representation and its Generation
- Annual Computer Security Applications Conference (ACSAC) 2019
- Sebastian Poeplau and Aurélien Francillon
- http://s3.eurecom.fr/tools/symbolic_execution/
- http://s3.eurecom.fr/docs/acsac19_poeplau.pdf
- https://hal.archives-ouvertes.fr/hal-02305914/
Scaling Symbolic Evaluation for Automated Verification of Systems Code with Serval
- SOSP 2019
- Luke Nelson, James Bornholt, Ronghui Gu, Andrew Baumann, Emina Torlak, Xi Wang
- https://unsat.cs.washington.edu/projects/serval/
- https://blog.acolyer.org/2019/11/13/scaling-symbolic-evaluation-serval/

Lectures & Courses

Foundations of Programming Languages
- M-PS (WS 2014/2015): Concepts of Programming Languages
- http://sepl.cs.uni-frankfurt.de/2014-ws/m-ps/index.en.html
- http://web.archive.org/web/http://sepl.cs.uni-frankfurt.de/2014-ws/m-ps/index.en.html
- lectures (videos & slides):
Static Program Analysis
- Anders Møller and Michael I. Schwartzbach
- https://cs.au.dk/~amoeller/spa/
- PLISS 2019 - Anders Møller
  - Static Program Analysis (part 1/2) - https://www.youtube.com/watch?v=Lr4cMmaJHrg
  - Static Program Analysis (part 2/2) - https://www.youtube.com/watch?v=6QQSIIvH-F0
25 Years of Program Analysis
- DEF CON 25 (2017) - Yan Shoshitaishvili (Zardus)
- https://www.youtube.com/watch?v=XL9kWQ3YpLo
- https://media.defcon.org/DEF%20CON%2025/DEF%20CON%2025%20presentations/DEFCON-25-Zardus-25-Years-of-Program-Analysis-UPDATED.pdf
Software Analysis and Testing - Mayur Naik
Program Analysis and Reliability - Nick Sumner, CMPT 886, Spring 2015, SFU
- Playlist: https://www.youtube.com/playlist?list=PLNC6lmsIySCOPjY8IwKBtD2cqe-MMgIGM
- Schedule & Slides: http://www.cs.sfu.ca/~wsumner/teaching/886/15/schedule.html
Program analysis for reverse engineers: from T to ⊥
- BSides Canberra 2018; Adrian Herrera
- https://www.youtube.com/watch?v=vOmGmjbVff4
- slides (not displayed in the video, may be a good idea to watch alongside):
  https://drive.google.com/file/d/1j9rfMt14pubi6G9PKK3akddyeet5bf0x/view
CS 252r: Advanced Topics in Programming Languages
- http://web-static-aws.seas.harvard.edu/courses/cs252/2011sp/
- https://www.seas.harvard.edu/courses/cs252/2015fa/schedule.html
A Gentle Introduction to Program Analysis
- Programming Languages Mentoring Workshop 2014
- Isıl Dillig (University of Texas)
- https://www.cis.upenn.edu/~alur/CIS673/isil-plmw.pdf

Software

SPARTA: a library that provides the basic blocks for building high-performance static code analyzers based on Abstract Interpretation
- https://github.com/facebookincubator/SPARTA
- SPARTA: a C++ library of software components for building high-performance static analyzers
- https://code.fb.com/open-source/sparta/
Bill Torpey - static analysis posts
- Static Analysis with Clang - http://btorpey.github.io/blog/2015/04/27/static-analysis-with-clang/
- Mo' Static - http://btorpey.github.io/blog/2016/04/07/mo-static/
- Even Mo' Static - http://btorpey.github.io/blog/2016/11/12/even-mo-static/
- Lots o' static - http://btorpey.github.io/blog/2017/09/17/lotso-static/

LLVM

awesome-llvm: A curated list of awesome LLVM related docs, tools, and other resources
- https://github.com/HongxuChen/awesome-llvm
LLVM Weekly - http://llvmweekly.org/
https://eli.thegreenplace.net/tag/llvm-clang
Building a Checker in 24 hours
- 2012 LLVM Developers’ Meeting; Anna Zaks, Jordan Rose
- https://llvm.org/devmtg/2012-11/Zaks-Rose-Checker24Hours.pdf
- https://www.youtube.com/watch?v=kdxlsP5QVPw
Code transformation and analysis using Clang and LLVM
- Static and Dynamic Analysis
- HPC Summer School 2017; Hal Finkel
- https://llvm.org/devmtg/2017-06/2-Hal-Finkel-LLVM-2017.pdf
- https://github.com/hfinkel/llvm-ss-2017
Compiler-assisted Performance Analysis
- 2016 LLVM Developers’ Meeting; Adam Nemet
- https://github.com/llvm-mirror/llvm/tree/master/tools/opt-viewer
- https://llvm.org/devmtg/2016-11/Slides/Nemet-Compiler-assistedPerformanceAnalysis.pdf
- https://www.youtube.com/watch?v=qq0q1hfzidg
Dg: LLVM Static Slicer
- Dependence graph for programs. A set of generic program analyses and a static slicer for LLVM bitcode
- https://github.com/mchalupa/dg
FPSCEV: Floating-Point Scalar Evolution in LLVM
LLVM Dataflow Info Printer Pass
- https://github.com/regehr/llvm-dataflow-info
- Tell us what some of LLVM's dataflow analyses think about the code being compiled.
- Testing Dataflow Analyses for Precision and Soundness
  - https://blog.regehr.org/archives/1709
- Testing Static Analyses for Precision and Soundness
  - CGO (Code Generation and Optimization) 2020
  - Jubi Taneja, Zhengyang Liu, John Regehr
  - http://www.cs.utah.edu/~regehr/cgo20.pdf
LLVM Debugging Tips and Tricks
- http://bholt.org/posts/llvm-debugging.html
Phasar - A LLVM-based static code analysis framework
- http://phasar.org/
- https://github.com/secure-software-engineering/phasar
- Static Analysis for C++ with Phasar
- https://pldi18.sigplan.org/event/pldi-2018-pldi-tutorials-static-analysis-for-c-with-phasar
- PhASAR: An Inter-Procedural Static Analysis Framework for C/C++
  - TACAS 2019
  - Philipp D. Schubert, Ben Hermann, Eric Bodden
  - http://www.thewhitespace.de/publications/shb19-phasar.pdf
SVF: Interprocedural Static Value-Flow Analysis in LLVM
- Pointer Analysis and Program Dependence Analysis for C and C++ Programs
- http://svf-tools.github.io/SVF/
- https://github.com/unsw-corg/SVF
- SVF: Interprocedural Static Value-Flow Analysis in LLVM
  - Compiler Construction (CC '16)
  - Yulei Sui and Jingling Xue
  - https://yuleisui.github.io/publications/cc16.pdf
  - 2016 EuroLLVM Developers' Meeting: Y. Sui "SVF: Static Value-Flow Analysis in LLVM"
  - https://www.youtube.com/watch?v=nD-i-enA8rc

LLVM - Symbolic Execution

haybale: Symbolic execution of LLVM IR with an engine written in Rust
- operates on LLVM IR, which allows it to analyze programs written in C/C++, Rust, Swift, or any other language which compiles to LLVM IR
- https://github.com/PLSysSec/haybale
KLEE Symbolic Virtual Machine

LLVM - Verification

LLBMC: The Low-Level Bounded Model Checker
- http://llbmc.org/
- http://llbmc.org/publications.html
- LLBMC: Bounded Model Checking of C and C++ Programs Using a Compiler IR
  - Verified Software: Theories, Tools and Experiments (VSTTE) 2012
  - Florian Merz, Stephan Falke, Carsten Sinz
  - https://doi.org/10.1007/978-3-642-27705-4_12
  - http://llbmc.org/files/papers/VSTTE12.pdf
  - http://llbmc.org/files/talks/vstte-2012.pdf
llrêve: Automatic regression verification for LLVM programs
- Automatically check programs for equivalence
- https://github.com/mattulbrich/llreve
- https://formal.iti.kit.edu/projects/improve/reve/
- Relational Program Reasoning Using Compiler IR – Combining Static Verification and Dynamic Analysis
  - Journal of Automated Reasoning 60(3) 2017
  - Moritz Kiefer, Vladimir Klebanov, Mattias Ulbrich
  - http://dx.doi.org/10.1007/s10817-017-9433-5
SAW: Software Analysis Workbench
- https://saw.galois.com/
- Constructing Semantic Models of Programs with the Software Analysis Workbench
  - Verified Software: Theories, Tools and Experiments (VSTTE) 2016
  - Robert Dockins, Adam Foltzer, Joe Hendrix, Brian Huffman, Dylan McNamee, Aaron Tomb
  - https://doi.org/10.1007/978-3-319-48869-1_5
SeaHorn Verification Framework: A fully automated analysis framework for LLVM-based languages
- http://seahorn.github.io/
- https://github.com/seahorn/seahorn
- http://seahorn.github.io/#publications
- The SeaHorn Verification Framework
  - Computer Aided Verification (CAV) 2015
  - A. Gurfinkel, T. Kahsai, A. Komuravelli, J.A.Navas
  - http://seahorn.github.io/papers/cav15.pdf
- A Context-Sensitive Memory Model for Verification of C/C++ Programs
  - Slides: http://seahorn.github.io/papers/sas17_slides.pdf
  - Paper: http://seahorn.github.io/papers/sea-dsa-SAS17.pdf
- Crab-llvm: Abstract Interpretation of LLVM bitcode
  - https://github.com/seahorn/crab-llvm
SMACK Software Verifier and Verification Toolchain
- http://smackers.github.io
- https://github.com/smackers/smack
- SMACK: Decoupling Source Language Details from Verifier Implementations
  - Computer Aided Verification (CAV) 2014
  - Zvonimir Rakamaric, Michael Emmi
  - https://soarlab.org/publications/2014_CAV_SMACK/
- SMACK Software Verification Toolchain
  - International Conference on Software Engineering (ICSE) Companion 2016
  - Montgomery Carter, Shaobo He, Jonathan Whitaker, Zvonimir Rakamaric, Michael Emmi
  - https://soarlab.org/publications/2016_ICSE_SMACK/
- Leveraging Compiler Intermediate Representation for Multi- and Cross-Language Verification
  - Verification, Model Checking, and Abstract Interpretation (VMCAI) 2020
  - Jack Garzella, Marek S. Baranowski, Shaobo He, Zvonimir Rakamaric
  - https://soarlab.org/publications/2020_vmcai_gbhr/

Clang

clang-tutor: A collection of Clang plugins - learn the API through examples
- https://github.com/banach-space/clang-tutor/
My First Clang Warning
- 2019 LLVM Developers’ Meeting
- Meike Baumgärtner, Dmitri Gribenko
- https://www.youtube.com/watch?v=FNnKMSkaLkY
- https://llvm.org/devmtg/2019-10/talk-abstracts.html#tut11

Clang Static Analyzer

Developing the Clang Static Analyzer
- 2019 LLVM Developers’ Meeting; Artem Dergachev
- https://www.youtube.com/watch?v=g0Mqx1niUi0
Faster, Stronger C++ Analysis with the Clang Static Analyzer
- 2018 LLVM Developers’ Meeting; George Karpenkov, Artem Dergachev
- https://www.youtube.com/watch?v=4n3l-ZcDJNY

Introduction

Building Program Reasoning Tools using LLVM and Z3
- POPL 2020 Tutorial
- Introduction to LLVM and Z3; Static Dataflow Analysis, Dynamic Symbolic Execution, Assertion Verification
- http://rightingcode.org/tutorials/popl20/
Getting Started With LLVM: Basics
- 2019 LLVM Developers’ Meeting; Jessica Paquette, Florian Hahn
- https://www.youtube.com/watch?v=3QQuhL-dSys
How to Contribute to LLVM
- 2019 LLVM Developers’ Meeting; Chris Bieneman, Kit Barton
- https://www.youtube.com/watch?v=C5Y977rLqpw
Introduction to LLVM
- 2019 LLVM Developers’ Meeting
- Eric Christopher & Johannes Doerfert
- https://www.youtube.com/watch?v=J5xExRGaIIY
- https://llvm.org/devmtg/2019-10/talk-abstracts.html#tut9
Intrinsics, Metadata, and Attributes: The story continues!
- 2016 LLVM Developers’ Meeting
- Hal Finkel, Argonne National Laboratory
- https://www.youtube.com/watch?v=jII0AcgU_5c
LLVM IR Tutorial - Phis, GEPs and other things, oh my!
- 2019 EuroLLVM Developers’ Meeting; Vince Bridgers, Felipe de Azevedo Piovezan (Intel)
- https://www.youtube.com/watch?v=m8G_S5LwlTo
LLVM Seminar - Northeastern+MIT
- 2019; Mike Shah
- http://www.mshah.io/#Talks
- https://www.youtube.com/playlist?list=PLvv0ScY6vfd8NDoT7qUab4VVAWV67oH-N
- Introduction to LLVM
- Introduction to Clang
  - https://www.youtube.com/watch?v=RAzre6PA-WI&list=PLvv0ScY6vfd8NDoT7qUab4VVAWV67oH-N
  - http://www.mshah.io/LLVM/NortheasternMITIntroductiontoClang.pdf
- Introduction to Program Analysis using LLVM
  - http://www.mshah.io/LLVM/NortheasternMITIntroductiontoProgramAnalysisusingLLVM.pdf
  - https://www.youtube.com/watch?v=w6SD3ramrwI&list=PLvv0ScY6vfd8NDoT7qUab4VVAWV67oH-N
Security Research and Development with LLVM - Andrew Reiter
clang-llvm-tutorial
- Clang and LLVM Tutorial Examples (AST Interpreter, Function Pointer Analysis, Value Range Analysis, Data-Flow Analysis, Andersen Pointer Analysis, LLVM Backend)
- https://github.com/lijiansong/clang-llvm-tutorial/
Custom Alias Analysis in LLVM
- https://blog.tartanllama.xyz/llvm-alias-analysis/
Introduction to LLVM: Building simple program analysis tools and instrumentation
- FOSDEM 2018 - Mike Shah
- https://fosdem.org/2018/schedule/event/introduction/
- https://www.youtube.com/watch?v=VKIv_Bkp4pk
- slides & code: http://www.mshah.io/fosdem18.html
LLVMPlayground: Small sample programs that use LLVM and Clang APIs.
- https://github.com/modocache/LLVMPlayground
Mapping High Level Constructs to LLVM IR
- https://github.com/f0rki/mapping-high-level-constructs-to-llvm-ir
- https://mapping-high-level-constructs-to-llvm-ir.readthedocs.io/
Nick Sumner's Examples
- slides: https://www.cs.sfu.ca/~wsumner/teaching/886/llvm.pdf
- llvm-demo: A simple example of how LLVM can be used to gather static or dynamic facts about a program.
  - https://github.com/nsumner/llvm-demo
- callgraph-profiler-template: A template for an introductory project on dynamic analysis using LLVM
  - https://github.com/nsumner/callgraph-profiler-template
- clang-plugins-demo: A simple example of defining custom plugins for Clang and the Clang Static Analyzer
  - https://github.com/nsumner/clang-plugins-demo
- llvm-dataflow-analysis: (very simple) static intraprocedural dataflow analyses
  - https://github.com/nsumner/llvm-dataflow-analysis
- overflower-template: Template for a project to teach basic static dataflow analysis using LLVM
  - https://github.com/nsumner/overflower-template
- path-profiler-template: A template for a path profiling project using LLVM
  - https://github.com/nsumner/path-profiler-template
Quarkslab blog
Writing a basic clang static analysis check
- https://bbannier.github.io/blog/2015/05/02/Writing-a-basic-clang-static-analysis-check.html

Instrumentation

Creating an LLVM Sanitizer from Hopes and Dreams
- https://blog.trailofbits.com/2019/06/25/creating-an-llvm-sanitizer-from-hopes-and-dreams/
- llvm-sanitizer-tutorial and documentation
  - https://github.com/trailofbits/llvm-sanitizer-tutorial
Instrew: Leveraging LLVM for High Performance Dynamic Binary Instrumentation
- VEE 2020
- Alexis Engelke, Martin Schulz
- https://conf.researchr.org/details/vee-2020/vee-2020-papers/5/Instrew-Leveraging-LLVM-for-High-Performance-Dynamic-Binary-Instrumentation
- https://github.com/aengelke/instrew
Loom: LLVM instrumentation library
- https://github.com/cadets/loom
PolyTracker: An LLVM-based instrumentation tool for universal taint analysis.
- https://github.com/trailofbits/polytracker
- https://blog.trailofbits.com/2019/11/01/two-new-tools-that-tame-the-treachery-of-files/
QBDI (QuarkslaB Dynamic binary Instrumentation): A Dynamic Binary Instrumentation framework based on LLVM
- https://qbdi.quarkslab.com
- https://github.com/quarkslab/QBDI
- 34C3 (2017) Implementing an LLVM based Dynamic Binary Instrumentation framework: https://events.ccc.de/congress/2017/Fahrplan/events/9006.html
- Example: plugging Triton on top of QBDI - http://shell-storm.org/repo/Notepad/qbdi_with_triton.txt
- A Preliminary Test of QBDI - https://www.johnfxgalea.com/2018/01/13/a-preliminary-test-of-qbdi/
- Example: SRAC - a Simple Return Address Checker - https://github.com/johnfxgalea/SRAC
sbt-instrumentation: Configurable instrumentation of LLVM bitcode
- https://github.com/staticafi/sbt-instrumentation
- Instrumentation of LLVM IR - https://is.muni.cz/th/409920/fi_m/?lang=en

Lifting

Lifting: Disassembly, Decompilation, Recompilation, Reverse Engineering

ANVILL Decompiler Toolchain
- ANVILL forges beautiful LLVM bitcode out of raw machine code
- https://github.com/lifting-bits/anvill
decomp: Compositional Decompilation using LLVM IR
- https://github.com/decomp/decomp
- Design documents: https://github.com/decomp/doc
llvm-mctoll
- This tool statically (AOT) translates (or raises) binaries to LLVM IR.
- https://github.com/Microsoft/llvm-mctoll
- Raising binaries to LLVM IR with MCTOLL
  - LCTES 2019 (WIP paper)
  - S. Bharadwaj Yadavalli, Aaron Smith
  - https://dl.acm.org/citation.cfm?id=3326354
  - https://conf.researchr.org/details/LCTES-2019/LCTES-2019-papers/15/Raising-Binaries-to-LLVM-IR-with-MCTOLL-Work-in-progress-
McSema: Framework for lifting x86, amd64, and aarch64 program binaries to LLVM bitcode
- https://www.trailofbits.com/research-and-development/mcsema/
- https://github.com/lifting-bits/mcsema
- Decompiling Binaries into LLVM IR Using McSema and Dyninst
  - https://is.muni.cz/th/pxe1j/?lang=en
Rellic: produces goto-free C output from LLVM bitcode
- Rellic is an implementation of the pattern-independent structuring algorithm to produce a goto-free C output from LLVM bitcode.
- https://github.com/lifting-bits/rellic
Rellume — Lifts x86-64 to LLVM IR
- https://github.com/aengelke/rellume
- Rellume is a lifter for x86-64 machine code to LLVM IR with focus on the performance of the lifted code. The generated LLVM IR can be compiled and executed again, for example using LLVM's JIT compiler, ideally having the same (or even better) performance as the original code.
Remill: Library for lifting of x86, amd64, and aarch64 machine code to LLVM bitcode
- https://github.com/lifting-bits/remill
RetDec: a retargetable machine-code decompiler based on LLVM
- https://retdec.com/
- https://github.com/avast-tl/retdec
revng: a static binary translator
- revng is a static binary translator. Given a input ELF binary for one of the supported architectures (currently MIPS, ARM and x86-64) it will analyze it and emit an equivalent LLVM IR. To do so, revng employs the QEMU intermediate representation (a series of TCG instructions) and then translates them to LLVM IR.
- https://rev.ng/
- https://github.com/revng/revng

Readings

A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs in the Real World
- Communications of the ACM, Vol. 53 No. 2, 2010
- Al Bessey, Ken Block, Ben Chelf, Andy Chou, Bryan Fulton, Seth Hallem, Charles Henri-Gros, Asya Kamsky, Scott McPeak, Dawson Engler
- https://cacm.acm.org/magazines/2010/2/69354-a-few-billion-lines-of-code-later/fulltext
Analysing the Program Analyser
- https://srg.doc.ic.ac.uk/publications/analyse-analyser-icse-v2025.html
Continuous Reasoning: Scaling the Impact of Formal Methods
- Logic in Computer Science (LISC) 2018; Peter O'Hearn
- https://research.fb.com/publications/continuous-reasoning-scaling-the-impact-of-formal-methods/
From Start-ups to Scale-ups: Opportunities and Open Problems for Static and Dynamic Program Analysis
- IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM) 2018
- Mark Harman, Peter O'Hearn
- https://research.fb.com/publications/from-start-ups-to-scale-ups-opportunities-and-open-problems-for-static-and-dynamic-program-analysis/
How to Prevent the next Heartbleed
- 2014; David A. Wheeler
- https://dwheeler.com/essays/heartbleed.html
Lessons from Building Static Analysis Tools at Google (2018)
- https://cacm.acm.org/magazines/2018/4/226371-lessons-from-building-static-analysis-tools-at-google/fulltext
Pointer analysis: haven't we solved this problem yet?
Righting Software
- IEEE Software, May 2004
- https://www.microsoft.com/en-us/research/publication/righting-software/
Source Code Analysis: A Road Map
- Future of Software Engineering (FOSE) 2007
- David Binkley
- https://dl.acm.org/citation.cfm?id=1254713
Static versus dynamic analysis---an illusory distinction?
- https://www.cs.kent.ac.uk/people/staff/srk21/blog/research/static-and-dynamic-analyses.html

Tags: reading language tool

Last modified 07 October 2024

Program analysis

A collection of links around program analysis

General

Symbolic Execution

Lectures & Courses

Software

LLVM

LLVM - Symbolic Execution

LLVM - Verification

Clang

Clang Static Analyzer

Introduction

Instrumentation

Lifting

Passes

Legacy Pass Manager

New Pass Manager

Readings