LiSTT-BN: Light-weight Static Taint Tracer for Binary Ninja

A Binary Ninja plugin implementing the LiSTT (Light-weight Static Taint Tracer) technique for scalable static taint flow analysis in binary executables.

About

This is a reimplementation of the research work "An Investigation into Unsound-incomplete Yet Practical Result Yielding Static Taintflow Analysis" (ARES 2014) by Sanjay Rawat, Laurent Mounier, and Marie-Laure Potet, using the Binary Ninja Python API.

Original Paper: LiSTT at ARES 2014

Original Implementation: github.com/tosanjay/listt (BinNavi-based)

What is LiSTT?

LiSTT is a lightweight static analysis technique designed to detect taint flows from input sources to vulnerable functions in binary code. Unlike traditional static analysis approaches that aim for complete soundness and completeness, LiSTT makes controlled compromises to achieve scalability on large real-world applications.

Key Features

• Scalable: Analyzes only relevant code slices instead of the entire program
• Practical: Designed for real-world large binaries (7000+ functions)
• Binary-level: Works directly on compiled executables
• Efficient: Uses call graph slicing to reduce analysis scope by 90%+

Core Algorithm

LiSTT works in three main steps:

1. Call Graph Slicing: For each pair (Input Source, Vulnerable Function), compute call graph slices containing only functions on paths between them
2. Intraprocedural Analysis (IntraDF): Compute function summaries tracking data dependencies between inputs/outputs
3. Interprocedural Analysis (InterDF): Propagate taint information using summaries to detect vulnerable flows

Controlled Compromises

To achieve scalability, LiSTT makes two key compromises:

1. Soundness: Uses default (over-approximate) summaries for functions outside slices → may produce false positives
2. Completeness: Limited tracking of global variables → may miss some flows

In practice (as shown in the paper), these compromises have minimal impact while dramatically improving performance.

Installation

Prerequisites

• Binary Ninja (version 3.0+)
• Python 3.7+

Install as Plugin

1. Linux/macOS:

cd ~/.binaryninja/plugins  # or ~/Library/Application\ Support/Binary\ Ninja/plugins on macOS
git clone https://github.com/tosanjay/Listt-BN.git

2. Windows:

cd %APPDATA%\Binary Ninja\plugins
git clone https://github.com/tosanjay/Listt-BN.git

3. Restart Binary Ninja

The plugin will appear under Plugins > LiSTT menu in Binary Ninja.

Usage

Method 1: Using the Plugin Menu (Recommended)

1. Open a binary in Binary Ninja
2. Go to Plugins > LiSTT > Run Taint Analysis
3. Wait for analysis to complete (progress shown in status bar)
4. View results in the markdown report

Method 2: Using the Utility Script (For Testing)

This method is useful for testing and debugging, or if you prefer working in the Python console.

1. Open a binary in Binary Ninja
2. Open the Python console (View > Python Console or press `)
3. Load and run the utility script:

# First, add the LiSTT-BN directory to Python path
import sys
sys.path.insert(0, '/path/to/Listt-BN')  # Use your actual path

# Load the script
exec(open('/path/to/Listt-BN/run_listt.py').read())

# Run analysis with default configuration (bv is automatically detected)
run_listt()

# Or run with verbose output
run_listt(verbose=True)

# Or run with custom sources/sinks
run_listt(input_sources=['fgets', 'recv'], vulnerable_functions=['strcpy'])

Alternative (if plugin is installed): If you've installed the plugin in Binary Ninja's plugin directory, you can import directly:

from listt_bn import LiSTTAnalyzer

analyzer = LiSTTAnalyzer(bv)
flows = analyzer.analyze()
print(analyzer.format_results(flows))

Utility Script Functions:

• run_listt(input_sources=None, vulnerable_functions=None, verbose=False) - Run analysis
• show_config() - Display current configuration
• add_custom_source(name) - Add custom input source
• add_custom_sink(name) - Add custom vulnerable function
• help_listt() - Show help information

Programmatic Usage

from listt_bn import LiSTTAnalyzer

# Get Binary Ninja BinaryView
bv = get_current_view()

# Create analyzer
analyzer = LiSTTAnalyzer(bv)

# Run analysis with default input sources and vulnerable functions
taint_flows = analyzer.analyze()

# Or specify custom functions
taint_flows = analyzer.analyze(
    input_sources=['custom_read_function'],
    vulnerable_functions=['custom_vulnerable_func']
)

# Print results
print(analyzer.format_results(taint_flows))

# Get statistics
stats = analyzer.get_summary_statistics()
print(f"Analyzed {stats['analyzed_functions']} functions")
print(f"Found {len(taint_flows)} taint flows")

Configuration

You can customize the analysis by modifying listt_bn/config.py or using the Config class:

from listt_bn import Config

# Add custom vulnerable function
Config.add_vulnerable_function('my_vulnerable_func')

# Add custom input source
Config.add_input_source('my_input_source')

# Adjust analysis parameters
Config.MAX_CALLGRAPH_DEPTH = 100
Config.USE_SSA_FORM = True
Config.VERBOSE = True

Architecture

Module Structure

listt_bn/
├── __init__.py              # Package initialization
├── config.py                # Configuration and function lists
├── function_summary.py      # Data structures for summaries
├── callgraph_slice.py       # Call graph slicing algorithm
├── intra_df.py              # Intraprocedural dataflow analysis
├── inter_df.py              # Interprocedural taint propagation
├── listt_analyzer.py        # Main analysis coordinator
└── plugin.py                # Binary Ninja plugin interface

Key Components

1. Call Graph Slicing (callgraph_slice.py)

Implements the S_r↔t algorithm to extract relevant function slices:

• Finds common root functions between input sources and vulnerable functions
• Computes upward slices (source → root)
• Computes downward slices (root → target)

2. Intraprocedural Analysis (intra_df.py)

Computes function summaries using MLIL SSA form:

• Tracks dependencies between function inputs and outputs
• Identifies tainted outputs and sensitive inputs
• Uses copy-propagation style dataflow analysis

3. Interprocedural Analysis (inter_df.py)

Propagates taint through function calls:

• Uses summaries to track taint across call boundaries
• Detects flows from input sources to vulnerable functions
• Reconstructs taint flow paths

Troubleshooting

Plugin Not Appearing in Menu

If you don't see the plugin under Plugins > LiSTT:

1. Check plugin directory: Make sure you cloned the repository into the correct plugins directory

   • Linux/macOS: ~/.binaryninja/plugins/
   • Windows: %APPDATA%\Binary Ninja\plugins\

2. Verify installation: The directory structure should look like:

   ~/.binaryninja/plugins/Listt-BN/
   ├── listt_bn/
   │   ├── __init__.py
   │   ├── plugin.py
   │   └── ...
   ├── __init__.py
   ├── run_listt.py
   └── README.md
   

3. Check the Python console for errors:

   • Open View > Python Console
   • Look for any error messages related to LiSTT
   • Common issues: missing dependencies, Python version mismatch

4. Use the Command Palette: Press Ctrl+P (or Cmd+P on macOS) and search for "LiSTT"

5. Use the utility script: If the plugin menu doesn't work, you can always use the utility script method (see Method 2 above)

Binary Ninja Version Compatibility

• LiSTT-BN requires Binary Ninja version 3.0 or later
• Check your version: Help > About Binary Ninja
• Some API features may differ between versions

Analysis Taking Too Long

• Large binaries (10,000+ functions) may take several minutes
• Enable verbose mode to see progress: run_listt(verbose=True)
• Check the Log window (View > Log) for progress messages

Built-in Function Lists

Input Sources (Taint Sources)

• File I/O: fgets, fread, read, ReadFile, etc.
• Network: recv, recvfrom, accept, etc.
• Standard input: scanf, fscanf, sscanf, etc.
• Environment: getenv, getopt, etc.

Vulnerable Functions (Taint Sinks)

• Buffer overflow prone: strcpy, strcat, sprintf, gets, etc.
• Memory operations: memcpy, memmove, bcopy
• Format strings: printf, fprintf, snprintf, etc.

See listt_bn/config.py for the complete list.

Examples

Example Output

LiSTT-BN Taint Flow Analysis Results
================================================================================
Total taint flows found: 2

Flow #1:
  Source: fgets @ 0x401234
  Sink: strcpy @ 0x401567
  Path (4 functions):
    1. main @ 0x401000
    2. read_input @ 0x401200
    3. fgets @ 0x401234
    4. strcpy @ 0x401567
  Variable flow: arg0 -> ret -> arg1 -> arg0

Flow #2:
  Source: recv @ 0x402100
  Sink: sprintf @ 0x402500
  Path (3 functions):
    1. handle_request @ 0x402000
    2. recv @ 0x402100
    3. sprintf @ 0x402500
  Variable flow: arg1 -> ret -> arg1

Performance

Based on the original paper's experiments:

Application	Functions	Analyzed	Time	Flows
muPDF	7,722	47 slices	25 min	6
FoxPlayer	1,074	14 slices	33 min	6
Serenity	559	1 slice	3 sec	1

The analysis achieves ~0.93-2.5% cyclomatic complexity compared to whole-program analysis, making it practical for large binaries.

Limitations

As per the paper's design:

1. Indirect calls: Limited support for complex indirect call patterns
2. Global variables: Only tracked in immediate predecessors of IS/VF
3. Completeness: May miss some taint flows (under-approximation)
4. Soundness: May report false positives (over-approximation)

These are intentional trade-offs for scalability.

Comparison with Original Implementation

Feature	Original (BinNavi)	LiSTT-BN
Platform	BinNavi + REIL IR	Binary Ninja + MLIL
Language	Python + Jython	Python 3
IR	REIL (3-address)	MLIL SSA
UI	Standalone tool	Binary Ninja plugin
Analysis	Same algorithm	Same algorithm

Development

Running Tests

# TODO: Add test suite
python -m pytest tests/

Contributing

Contributions are welcome! Areas for improvement:

• Better indirect call resolution
• Enhanced global variable tracking
• Custom UI for configuration
• Additional vulnerability patterns (use-after-free, etc.)
• Path constraint solving integration
• Export to other tools (e.g., fuzzer input)

Citation

If you use LiSTT-BN in your research, please cite the original paper:

@inproceedings{rawat2014listt,
  title={LiSTT: An Investigation into Unsound-incomplete Yet Practical Result Yielding Static Taintflow Analysis},
  author={Rawat, Sanjay and Mounier, Laurent and Potet, Marie-Laure},
  booktitle={2014 Ninth International Conference on Availability, Reliability and Security},
  pages={498--505},
  year={2014},
  organization={IEEE}
}

License

MIT License - see LICENSE file for details.

Authors

• Sanjay Rawat - Original research and implementation
• Implementation based on the ARES 2014 paper by Rawat, Mounier, and Potet

Acknowledgments

• Original LiSTT implementation: https://github.com/tosanjay/listt
• Binary Ninja API documentation: https://api.binary.ninja/
• The BINSEC project (ANR-12-INSE-0002-01) for funding the original research

Support

For issues, questions, or contributions:

• GitHub Issues: https://github.com/tosanjay/Listt-BN/issues
• Original paper: See docs/LiSTT-rawat2014.pdf

---

Note: This is a research prototype for vulnerability analysis and security testing. Use responsibly and only on binaries you have permission to analyze.