BinTuner is a cost-efficient auto-tuning framework, which can deliver a near-optimal binary code that reveals much more differences than -Ox settings.

BinTuner

Last update: Dec 16, 2022

Related tags

Data Analysis Dev

Overview

BinTuner

BinTuner is a cost-efficient auto-tuning framework, which can deliver a near-optimal binary code that reveals much more differences than -Ox settings. it also can assist the binary code analysis research in generating more diversified datasets for training and testing. The BinTuner framework is based on OpenTuner, thanks to all contributors for their contributions.

The architecture of BinTuner:

The core on the server-side is a metaheuristic search engine (e.g., the genetic algorithm), which directs iterative compilation towards maximizing the effect of binary code differences.

The client-side runs different compilers (GCC, LLVM ...) and the calculation of the fitness function.

Both sides communicate valid optimization options, fitness function scores, and compiled binaries to each other, and these data are stored in a database for future exploration. When BinTuner reaches a termination condition, we select the iterations showing the highest fitness function score and output the corresponding binary code as the final outcomes.

System dependencies

A list of system dependencies can be found in packages-deps which are primarily python 2.6+ (not 3.x) and sqlite3.

On Ubuntu/Debian there can be installed with:

sudo apt-get update
sudo apt-get upgrade
sudo apt-get install `cat packages-deps | tr '\n' ' '`

Installation

Running it out of a git checkout, a list of python dependencies can be found in requirements.txt these can be installed system-wide with pip.

sudo apt-get install python-pip
sudo pip install -r requirements.txt

If you encounter an error message like this:

Could not find a version that satisfies the requirement fn>=0.2.12 (from -r requirements.txt (line 2)) (from versions:)
No matching distribution found for fn>=0.2.12 (from -r requirements.tet (line 2))

Please try again or install each manually

pip install fn>=0.2.12
...
pip install numpy>=1.8.0
...

If you encounter an error message like this:

ImportError: No module named lzma

Please install lzma

sudo apt-get install python-lzma

If you encounter an error message like this:

assert compile_result['returncode'] == 0
AssertionError

Please confirm how to use the compiler in your terminal, such as GCC or gcc-10.2.0 it needs to be modified in your .Py file

If you encounter an error message like this:

sqlalchemy.exc.OperationalError: (pysqlite2.dbapi2.OperationalError) database is locked [SQL: u'INSERT INTO tuning_run (uuid, program_version_id, machine_class_id, input_class_id, name, args, objective, state, start_date, end_date, final_config_id) VALUES (?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?)'] [parameters: ('b3311f3609ff4ce9aa40c0f9bb291d26', 1, None, None, 'unnamed', 
   
   
    
    , 
    
    
     
     , 'QUEUED', '2021-xx-xx 03:42:04.145932', None, None)] (Background on this error at: http://sqlalche.me/e/e3q8)

Just delete the DB file saved before (PATH:/examples/gccflags/opentuner.db/Your PC's Name.db).

Install Compiler

GCC

Check to see if the compiler is installed

e.g.

gcc -v  shows that
gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04)

Please note that there have different optimization options in different versions of compilers.

If you use the optimization options that are not included in this version of the compiler, the program can not run and report an error.

It is strongly recommended to confirm that the optimization options are in the official instructions of GCC or LLVM before using them.

e.g. GCC version 10.2.0.

You can also use the command to display all options in terminal

gcc --help=optimizers


The following options control optimizations:
  -O
   
   
    
                      Set optimization level to 
    
    
     
     .
  -Ofast                      Optimize for speed disregarding exact standards
                              compliance.
  -Og                         Optimize for debugging experience rather than
                              speed or size.
  -Os                         Optimize for space rather than speed.
  -faggressive-loop-optimizations Aggressively optimize loops using language
                              constraints.
  -falign-functions           Align the start of functions.
  -falign-jumps               Align labels which are only reached by jumping.
  -falign-labels              Align all labels.
  -falign-loops               Align the start of loops.
  ...

LLVM

clang -v

Check how to install LLVM here

https://apt.llvm.org/

https://clang.llvm.org/get_started.html

Checking Installation

Enter the following command in terminal to test:

eg@xx:~/BinTuner/examples/gccflags$ python main.py 2

You will see some info like this:

Program Start
************************ Z3 ************************
5- Result--> Unavailable
3- Result--> Available
[ Z3 return Results = first second True four False]
[ Changed "shrink-wrap" value ]
...
-------------------------------------------------

--- BinTuner ---
--- Command lines and compiler optimization options ---:
gcc benchmarks/bzip2.c -lm -o ./tmp0.bin -O3 -fauto-inc-dec -fbranch-count-reg -fno-combine-stack-adjustments 
-fcompare-elim -fcprop-registers -fno-dce -fdefer-pop -fdelayed-branch -fno-dse -fforward-propagate -fguess-branch-probability 
-fno-if-conversion2 -fno-if-conversion -finline-functions-called-once -fipa-pure-const -fno-ipa-profile -fipa-reference 
-fno-merge-constants -fmove-loop-invariants -freorder-blocks -fshrink-wrap -fsplit-wide-types -fno-tree-bit-ccp -fno-tree-ccp 
-ftree-ch -fno-tree-coalesce-vars -ftree-copy-prop -ftree-dce -fno-tree-dse -ftree-forwprop -fno-tree-fre -ftree-sink -fno-tree-slsr 
-fno-tree-sra -ftree-pta -ftree-ter -fno-unit-at-a-time -fno-omit-frame-pointer -ftree-phiprop -fno-tree-dominator-opts -fno-ssa-backprop 
-fno-ssa-phiopt -fshrink-wrap-separate -fthread-jumps -falign-functions -fno-align-labels -fno-align-labels -falign-loops -fno-caller-saves 
-fno-crossjumping -fcse-follow-jumps -fno-cse-skip-blocks -fno-delete-null-pointer-checks -fno-devirtualize -fdevirtualize-speculatively 
-fexpensive-optimizations -fno-gcse -fno-gcse-lm -fno-hoist-adjacent-loads -finline-small-functions -fno-indirect-inlining -fipa-cp 
-fipa-sra -fipa-icf -fno-isolate-erroneous-paths-dereference -fno-lra-remat -foptimize-sibling-calls -foptimize-strlen 
-fpartial-inlining -fno-peephole2 -fno-reorder-blocks-and-partition -fno-reorder-functions -frerun-cse-after-loop -fno-sched-interblock 
-fno-sched-spec -fno-schedule-insns -fno-strict-aliasing -fstrict-overflow -fno-tree-builtin-call-dce -fno-tree-switch-conversion 
-ftree-tail-merge -ftree-pre -fno-tree-vrp -fno-ipa-ra -freorder-blocks -fno-schedule-insns2 -fcode-hoisting -fstore-merging 
-freorder-blocks-algorithm=simple -fipa-bit-cp -fipa-vrp -fno-inline-functions -fno-unswitch-loops -fpredictive-commoning 
-fno-gcse-after-reload -fno-tree-loop-vectorize -ftree-loop-distribute-patterns -fno-tree-slp-vectorize -fvect-cost-model 
-ftree-partial-pre -fpeel-loops -fipa-cp-clone -fno-split-paths -ftree-vectorize --param early-inlining-insns=526 
--param gcse-cost-distance-ratio=12 --param iv-max-considered-uses=762
 -O3
--NCD:0.807842390787
---Test----
--Max:0
--Current:0
--Count:0
...

Results

The DB file saved in the PATH:/examples/gccflags/opentuner.db/Your PC's Name.db

Each sequence of compilation flags and the corresponding ncd value are saved in the db file.

Set up how many times to run

Please refer to the settings in main.py There are two strategies The default setting runs 100 times, if you want to modify it according to your own wishes this is ok. For example, by monitoring the change of NCD value in 100 times, if the cumulative change of 100 times increase is less than 5%, let's terminte it.

First-order formulas

We manually generate first-order formulas after understanding the compiler manual. The knowledge we learned is easy to move between the same compiler series---we only need to consider the different optimization options introduced by the new version.

We use Z3 Prover to analyze all generated optimization option sequences for conflicts and make changes to conflicting options for greater compiling success.

For more details, please refer Z3Prover.

Setting for Genetic Algorithm

The genetic algorithm is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms. Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover, and selection.

We tune four parameters for the genetic algorithm, including mutation_rate, crossover_rate, must_mutate_count, crossover_strength.

For more details, please refer globalGA.

Future Work

We are studying constructing custom optimization sequences that present the best tradeoffs between multiple objective functions (e.g., execution speed & NCD). To further reduce the total iterations of BinTuner, an exciting direction is to develop machine learning methods that correlate C language features with particular optimization options. In this way, we can predict program-specific optimization strategies that achieve the expected binary code differences.

Comments

Cannot run the example in README
Hi, I'm trying to run the bzip2 example mentioned in README.md. Under the Dev/BinTuner/examples/gccflags directory, I tried to run the command python2 bzip2_gcc.py 10. Then Python complains the file Dev/BinTuner/examples/gccflags/../../opentuner/utils/adddeps.py cannot be found. I manually looked up the source directory and also could not find the file adddeps.py.

The full error information is attached:

Traceback (most recent call last): File "bzip2_gcc.py", line 3, in <module> import adddeps File "/...../Dev/BinTuner/examples/gccflags/adddeps.py", line 6, in <module> execfile(target, dict(__file__=target)) IOError: [Errno 2] No such file or directory: '/....../Dev/BinTuner/examples/gccflags/../../open tuner/utils/adddeps.py'

Thanks, XZ-X
opened by XZ-X 12
z3 crashes in running the example in the README

Program Start ['GGA'] beformutation ************************ Z3 ************************

Thread 1 "python" received signal SIGSEGV, Segmentation fault. api::object::inc_ref (this=this@entry=0xffffffff918ba0a8) at /z3/src/api/api_context.cpp:38 38 void object::inc_ref() { m_ref_count++; } (gdb) bt #0 api::object::inc_ref (this=this@entry=0xffffffff918ba0a8) at /z3/src/api/api_context.cpp:38 #1 0x00007f451a0f0c88 in Z3_solver_inc_ref (c=0x55a49197c7a8, s=0xffffffff918ba0a8) at /z3/src/api/api_solver.cpp:379 #2 0x00007f45bd37cdae in ffi_call_unix64 () from /usr/lib/x86_64-linux-gnu/libffi.so.6 #3 0x00007f45bd37c71f in ffi_call () from /usr/lib/x86_64-linux-gnu/libffi.so.6 #4 0x00007f45bd58fbf4 in _ctypes_callproc () from /usr/lib/python2.7/lib-dynload/_ctypes.x86_64-linux-gnu.so #5 0x00007f45bd58f5f5 in ?? () from /usr/lib/python2.7/lib-dynload/_ctypes.x86_64-linux-gnu.so #6 0x000055a4902da6c0 in PyEval_EvalFrameEx () #7 0x000055a4902da4c6 in PyEval_EvalFrameEx () #8 0x000055a4902d2d5a in PyEval_EvalCodeEx () #9 0x000055a4902eebc9 in ?? () #10 0x000055a490306efe in ?? () #11 0x000055a4902be8be in PyObject_Call () #12 0x000055a4902f23cc in PyInstance_New () #13 0x000055a4902da6c0 in PyEval_EvalFrameEx () #14 0x000055a4902d2d5a in PyEval_EvalCodeEx () #15 0x000055a4902dae3c in PyEval_EvalFrameEx () #16 0x000055a4902da4c6 in PyEval_EvalFrameEx () #17 0x000055a4902da4c6 in PyEval_EvalFrameEx () #18 0x000055a4902d2d5a in PyEval_EvalCodeEx () #19 0x000055a4902dae3c in PyEval_EvalFrameEx () #20 0x000055a4902d2d5a in PyEval_EvalCodeEx () #21 0x000055a4902dae3c in PyEval_EvalFrameEx () #22 0x000055a4902da4c6 in PyEval_EvalFrameEx () #23 0x000055a4902da4c6 in PyEval_EvalFrameEx () #24 0x000055a4902d2d5a in PyEval_EvalCodeEx () #25 0x000055a4902dae3c in PyEval_EvalFrameEx () #26 0x000055a4902d2d5a in PyEval_EvalCodeEx () #27 0x000055a4902d2899 in PyEval_EvalCode () #28 0x000055a4903030ef in ?? () #29 0x000055a4902fe2f2 in PyRun_FileExFlags () #30 0x000055a4902fdded in PyRun_SimpleFileExFlags () #31 0x000055a4902acc99 in Py_Main () #32 0x00007f45bf87fbf7 in __libc_start_main (main=0x55a4902ac710
, argc=3, argv=0x7ffec001b838, init=, fini=, rtld_fini=, stack_end=0x7ffec001b828) at ../csu/libc-start.c:310 #33 0x000055a4902ac62a in _start ()

opened by chenju2k6 4
Strategies for running BinTuner much faster without much compromises
Currently BinTuner focuses on quality. To make it a practical tool, it'd need to provide subsecond answers for small programs (say 1000 SLOC of C).

Please share your ideas here how could that be achieved without much compromising the quality of the outcomes.

Based on some fast heuristics (e.g. based on experience with "BinTuning" of previous apps) or source code available or some annotations in debug build or whatever, choose only a very small percentage (maybe less than 0.5%) of all instructions at interesting places and run BinTuner only on those.

Restrict or extend the operations the genetic algorithm can do leading to faster convergence.

Pre-prepare the binary in some way so that the initial phases the genetic algorithm currently does can be "skipped". In other words, shuffle with the instructions before the genetic algorithm starts in a way resembling the first few hundreds/thousands iterations/populations of the genetic algorithm but in one step. Yet in other words, prepare quickly more optimal default initial state of the input instead of relying on the genetic algorithm all the way down from the very beginning.

Techniques used by superoptimizers.
opened by dumblob 4
How to use BinTuner

Hello, thanks for your execellent research and friendly released code. However, it seems you do not mention how to use this this tool to get the nearly optimal compiler flags to create binaries. May I ask whether you will detial the steps to use BinTuner? Thanks in advance.

opened by randomFriendlyGuy 3
Question about optimization options of clang

Could I asked a question. GCC is used as the optimization option in the original code. The paper also conducted experiments on llvm optimization options. What specific optimization options are used?

opened by lxw-1006 2
Set up how many times to run

Hi, I am compiling the SPEC using main_clang.py. Basically, I can generate the tuned binary, which is exciting :) After that, I am wondering how to set the termination condition. From the README and the main_clang.py, there are two paths monitoring the change of MAX value. After the MAX value remains unchanged 10 times, the increase is less than 0.05 for 10 times, or the sum of trigger time of these two conditions has reached 10, it would terminate. So what's the argument (for the command "python main.py 10" is 10) used for? I have changed it to 100 but the termination is still triggered by the above two paths. Should I change the termination threshold to higher, like 100, or 10 is enough? Thanks for your time and have a nice day!

opened by Patrick-ICT 1
How to specify compiler options for LLVM

Hello, I was interested to run the LLVM version of BinTuner but cannot find any related files for compiling via clang. is there an equivalent python file that compiles using clang similar to examples/gccflags ? Are there instructions on how to specify constraints for LLVM options and get the correct combination of options for clang?

opened by vid-999 1
About Constraints between GCC Options

Hello, I am very interested in your work. At present, I have encountered a problem. When I compiler benchmarks with GCC, I turn on the specified single or several optimization options based on -O0. Unfortunately, I found that the optimization options did not work. I noticed that in your paper it is mentioned that "In some cases, two options negatively influence each other, and turning on them together leads to a compilation error. Some other compilation options only work when a certain option has been activated. For example, -fpartial-inlining has any effect only when -finline-functions is turned on. To avoid compilation errors caused by such constraints, we manually translate them into logical first-order formulas offline after understanding the compiler manual.".

I can't find the constraint file in the code https://github.com/BinTuner/Dev , could you please share it with me? Also, do you have any good suggestions to solve this problem? Thank you!

opened by orangehn 1
Question about Z3 solver used.

Hello, thanks for your fancy research and your code. There is one question bother me: I mention that you only deal with GCC Flags i n the source code of BinTuner, but in the paper, you use both GCC and Clang.

Both LLVM and GCC explicitly specify a set of constraints between optimization ?ags, including adverse interactions and dependency relationships.

I check their website and find that it's clear in GCC, but nobody mentioned this kind of interaction in LLVM.

So does that mean there's no such interaction? Or it's just so hard for us to figure it out?

I would appreciate it if you could help me with this.

opened by tszdanger 1

Owner

BinTuner

BinTuner is a cost-efficient auto-tuning framework, which can deliver a near-optimal binary code that reveals much more differences than -Ox settings.

GitHub

Evidence enables analysts to deliver a polished business intelligence system using SQL and markdown.

Evidence enables analysts to deliver a polished business intelligence system using SQL and markdown

915 Dec 26, 2022

Python utility to extract differences between two pandas dataframes.

8 Jan 7, 2023

Python Kalman filtering and optimal estimation library. Implements Kalman filter, particle filter, Extended Kalman filter, Unscented Kalman filter, g-h (alpha-beta), least squares, H Infinity, smoothers, and more. Has companion book 'Kalman and Bayesian Filters in Python'.

FilterPy - Kalman filters and other optimal and non-optimal estimation filters in Python. NOTE: Imminent drop of support of Python 2.7, 3.4. See secti

2.5k Dec 30, 2022

Produces a summary CSV report of an Amber Electric customer's energy consumption and cost data.

Amber Electric Usage Summary This is a command line tool that produces a summary CSV report of an Amber Electric customer's energy consumption and cos

12 May 26, 2022

A neural-based binary analysis tool

A neural-based binary analysis tool Introduction This directory contains the demo of a neural-based binary analysis tool. We test the framework using

208 Dec 22, 2022

An Indexer that works out-of-the-box when you have less than 100K stored Documents

U100KIndexer An Indexer that works out-of-the-box when you have less than 100K stored Documents. U100K means under 100K. At 100K stored Documents with

7 Mar 15, 2022

A python package which can be pip installed to perform statistics and visualize binomial and gaussian distributions of the dataset

GBiStat package A python package to assist programmers with data analysis. This package could be used to plot : Binomial Distribution of the dataset p

4 Oct 17, 2022

Elementary is an open-source data reliability framework for modern data teams. The first module of the framework is data lineage.

Data lineage made simple, reliable, and automated. Effortlessly track the flow of data, understand dependencies and analyze impact. Features Visualiza

898 Jan 9, 2023

Pandas-based utility to calculate weighted means, medians, distributions, standard deviations, and more.

weightedcalcs weightedcalcs is a pandas-based Python library for calculating weighted means, medians, standard deviations, and more. Features Plays we

98 Dec 31, 2022

Used for data processing in machine learning, and help us to construct ML model more easily from scratch

Used for data processing in machine learning, and help us to construct ML model more easily from scratch. Can be used in linear model, logistic regression model, and decision tree.

0 Jul 5, 2022

A highly efficient and modular implementation of Gaussian Processes in PyTorch

GPyTorch GPyTorch is a Gaussian process library implemented using PyTorch. GPyTorch is designed for creating scalable, flexible, and modular Gaussian

3k Jan 2, 2023

Powerful, efficient particle trajectory analysis in scientific Python.

freud Overview The freud Python library provides a simple, flexible, powerful set of tools for analyzing trajectories obtained from molecular dynamics

195 Dec 20, 2022

Tuplex is a parallel big data processing framework that runs data science pipelines written in Python at the speed of compiled code

Tuplex is a parallel big data processing framework that runs data science pipelines written in Python at the speed of compiled code. Tuplex has similar Python APIs to Apache Spark or Dask, but rather than invoking the Python interpreter, Tuplex generates optimized LLVM bytecode for the given pipeline and input data set.

791 Jan 4, 2023

Recommendations from Cramer: On the show Mad-Money (CNBC) Jim Cramer picks stocks which he recommends to buy. We will use this data to build a portfolio

Backtesting the "Cramer Effect" & Recommendations from Cramer Recommendations from Cramer: On the show Mad-Money (CNBC) Jim Cramer picks stocks which

12 Aug 30, 2022

PostQF is a user-friendly Postfix queue data filter which operates on data produced by postqueue -j.

11 Nov 24, 2022

Datashredder is a simple data corruption engine written in python. You can corrupt anything text, images and video.

Datashredder is a simple data corruption engine written in python. You can corrupt anything text, images and video. You can chose the cha

2 Jul 22, 2022

Data Competition: automated systems that can detect whether people are not wearing masks or are wearing masks incorrectly

Table of contents Introduction Dataset Model & Metrics How to Run Quickstart Install Training Evaluation Detection DATA COMPETITION The COVID-19 pande

1 Feb 27, 2022

A set of procedures that can realize covid19 virus detection based on blood.

3 Mar 7, 2022

songplays datamart provide details about the musical taste of our customers and can help us to improve our recomendation system

Songplays User activity datamart The following document describes the model used to build the songplays datamart table and the respective ETL process.

1 Jul 13, 2021