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,

c 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

c 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
• Manual: Tool user guide with detailed examples and discussion.
• Demo: online demo and input examples

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

   shell 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):

   shell python3 -m venv venv source venv/bin/activate

   Install required packages:

   shell python -m pip install -r requirements.txt

   For development, install dev-dependencies instead:

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

   :b:   Using Docker↗

   Build a container -- also installs dev-dependencies:

   shell docker build . -t pymwp

   Run the container:

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

3. Run the analysis

   From project root run:

   shell python -m pymwp path/to_some_file.c

   for example:

   shell python -m pymwp c_files/basics/if.c

   for all available options and help, run:

   shell python -m pymwp

Evaluation

These options are available when running from source.

make bench # run benchmark of all c_files examples make test # run unit tests on pymwp source code make profile # run cProfile on all c_files examples