pymwp: MWP analysis in Python

pymwp is a tool for automatically performing static analysis on programs written in C. It analyzes resource usage and determines if a program's variables growth rates are no more than polynomially related to their inputs sizes.

For example,

   int main(int X1, int X2, int X3){
       X1 = X2 + X3;
       X1 = X1 + X1;
   }

is satisfactory because—between the initial variable values (Xi) and the final values (Xi')—all variables have a polynomially bounded data-flow (omitting constants): X1' ≤ X2+X3 and X2' ≤ X2 and X3' ≤ X3. pymwp derives this bound automatically (⯈ demo).

However, program

   int main(int X1, int X2, int X3){
      X1 = 1;
      while (X2 > 0){ X1 = X1 + X1; }
   }   

fails the analysis, because X1 grows exponentially (X1' = $2^{\texttt{X2}}$). pymwp reports a program is infinite when no polynomial bound can be derived (⯈ demo).

pymwp is inspired by "A Flow Calculus of mwp-Bounds for Complexity Analysis". Try our online demo to see it action. For more details, see pymwp documentation, particularly supported C language features.

Documentation and Demo

Documentation: statycc.github.io/pymwp

Demo: online demo and input examples

Publication: "pymwp: A Static Analyzer Determining Polynomial Growth Bounds", also on HAL.

Tool user guide: statycc.github.io/.github/pymwp with detailed examples and discussion.

The user guide is the ideal place to start for a general and interactive introduction to pymwp.

Installation

Install the latest release from PyPI

pip install pymwp

How to Use

Command-Line Use

To analyze a C file, run in terminal:

pymwp path/to_some_file.c

For a list of available command options and help, run:

pymwp

Use in Python Scripts

You can also use pymwp by importing it in a Python script. See modules documentation for details and examples.

Running from source

If you want to use the latest stable version—possibly ahead of the latest release, and with special evaluation utilities and input examples—use pymwp directly from source.

1. Clone the repository

   git clone https://github.com/statycc/pymwp.git 
   cd pymwp

2. Set up Python runtime environment of preference

   :a:   Using Python venv↗

   Create and activate a virtual environment (POSIX bash/zsh):

   python3 -m venv venv
   source venv/bin/activate

   Install required packages:

   python -m pip install -r requirements.txt

   For development, install dev-dependencies instead:

   python -m pip install -r requirements-dev.txt

   :b:   Using Docker↗

   Build a container -- also installs dev-dependencies:

   docker build . -t pymwp

   Run the container:

   docker run --rm -v "$(pwd):$(pwd)" pymwp

3. Run the analysis

   From project root run:

   python -m pymwp path/to_some_file.c

   for example:

   python -m pymwp c_files/basics/if.c

   for all available options and help, run:

   python -m pymwp

## Evaluation These options are available when running from source. ``` make bench # run benchmarks on all examples make test # run all unit tests on pymwp source code make profile # run cProfile on all examples ```