opt_fuzz.py 8.05 KB
Newer Older
Bowen Wu's avatar
Bowen Wu committed
1
2
3
4
5
6
7
8
9
10
import time
import random
import os
import math
import pickle

from typing import List
from queue import Queue

from generator import MPSProgram
Ambi's avatar
Ambi committed
11
from mps_mut import DenseMatMut, ScaleMut, SparseMatMut, FlipSignMut, NoOpMut
Bowen Wu's avatar
Bowen Wu committed
12
13
14
15
16
17
18
19
from mps_util import load_mps_dict
from optimizer import OPTIMAL, CplexSolver, GurobiSolver

# TODO
# 1. Make this class checkpoint-able
# 2. Use two threads for cplex and gurobi each
# 3. Collect more stats
class OptFuzzer(object):
20
    MAX_MUTANTS_IN_DIR = 10
Bowen Wu's avatar
Bowen Wu committed
21
    def __init__(self, seed : List, mut_method : List, cplex : CplexSolver, gurobi : GurobiSolver, 
Ambi's avatar
Ambi committed
22
                save_path : str, checkpoint_freq : int, checkpoint_path : str, diff_path: str, abs_tol = 1e-6) -> None:
Bowen Wu's avatar
Bowen Wu committed
23
24
        self.seed = seed # a list of seed mps in dict format
        self.mut_method = mut_method # a list of mutation methods
Ambi's avatar
Ambi committed
25
        self.no_op_mut_method = NoOpMut()
Bowen Wu's avatar
Bowen Wu committed
26
27
28
29
30
31
32
33
34
35
36
        self.next_mut = 0
        self.n_mut = len(self.mut_method)
        self.cplex = cplex # cplex solver
        self.gurobi = gurobi # gurobi solver
        self.save_path = save_path # path to save the mutated mps files
        os.makedirs(self.save_path, exist_ok=True)
        self.checkpoint_freq = checkpoint_freq
        self.checkpoint_path = checkpoint_path # path to store the checkpoint files
        os.makedirs(self.checkpoint_path, exist_ok=True)
        self.diff_path = diff_path # path to store the mutants that cause differences
        os.makedirs(self.diff_path, exist_ok=True)
Ambi's avatar
Ambi committed
37
        self.abs_tol = abs_tol
Bowen Wu's avatar
Bowen Wu committed
38
39
40
41
        self.diff = [] # mutants that cause differences
        self.all_mutant = []
        self.queue = Queue(maxsize=0) # unbounded queue for seeds
        self.next_id = 0 # id assigned to the next mutant
Ambi's avatar
Ambi committed
42
        print("Initializing seeds")
Bowen Wu's avatar
Bowen Wu committed
43
44
45
46
47
        for s in self.seed:
            mutant = {
                "id" : self.next_id,
                "parent" : [-1], # root seed, no parent
                "mut_method" : "",
Ambi's avatar
Ambi committed
48
49
                "mps" : load_mps_dict(s),
                "name": s,
Bowen Wu's avatar
Bowen Wu committed
50
51
52
            }
            self.next_id += 1
            self.queue.put_nowait(mutant)
Ambi's avatar
Ambi committed
53
        print("Seeds initialized")
Bowen Wu's avatar
Bowen Wu committed
54

Ambi's avatar
Ambi committed
55
    def get_mutant(self, mut_choice : str, nr_mutations: int = 4) -> dict:
Bowen Wu's avatar
Bowen Wu committed
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
        parent = self.queue.get()
        mps = parent["mps"]
        idx = 0
        
        if mut_choice == "fixed":
            idx = 0
        elif mut_choice == "round_robin":
            idx = self.next_mut
            self.next_mut = (self.next_mut + 1) % self.n_mut
        elif mut_choice == "random":
            idx = random.randint(0, self.n_mut - 1)
        else:
            print(f"Unsupported mutant choice {mut_choice}")
            os.abort()
        
Ambi's avatar
Ambi committed
71
        #print("========== GOING TO MUTATE ============")
Ambi's avatar
Ambi committed
72
73
74
75
76
77
78
79
80
81
        if mut_choice == 'random':
            mps_prime = mps
            for _ct in range(nr_mutations):
                idx = random.randint(0, self.n_mut - 1)
                mut_method = self.no_op_mut_method if (random.random() < 0.5) else self.mut_method[idx]
                print('Mutating using ', mut_method)
                mps_prime = mut_method(mps_prime)
        else:
            mps_prime = self.mut_method[idx](mps)

Bowen Wu's avatar
Bowen Wu committed
82
83
        ret = {
            "id" : self.next_id,
Ambi's avatar
Ambi committed
84
            "seed_name": parent["name"],
Bowen Wu's avatar
Bowen Wu committed
85
86
87
88
89
90
91
92
93
94
95
            "parent" : [parent["id"]], # root seed, no parent
            "mut_method" : self.mut_method[idx].__str__(),
            "mps" : mps_prime
        }

        self.next_id += 1

        self.queue.put(parent)

        return ret
    
96
    def sol_equal(self, sol1 : dict, sol2 : dict, check_var = False) -> bool:
Bowen Wu's avatar
Bowen Wu committed
97
98
99
100
101
        if sol1['status'] != sol2['status']:
            return False
        
        if sol1['status'] == OPTIMAL:
            # check if the obj value is the same
Ambi's avatar
Ambi committed
102
            if not math.isclose(sol1['obj_val'], sol2['obj_val'], abs_tol=self.abs_tol):
Bowen Wu's avatar
Bowen Wu committed
103
104
105
                return False
            
            # check if the variable values are the same
106
107
108
109
110
111
            # not applicable to MIP where continuous var values can be approx.
            if check_var:
                for v1 in sol1['var_val']:
                    var1 = sol1['var_val'][v1]
                    
                    # Gurobi omits variables if 0
Bowen Wu's avatar
Bowen Wu committed
112
                    var2 = 0
113
114
115
116
117
                    try:
                        var2 = sol2['var_val'][v1]
                    except KeyError:
                        var2 = 0
                    
Ambi's avatar
Ambi committed
118
                    if not math.isclose(var1, var2, abs_tol=self.abs_tol):
119
                        return False
Bowen Wu's avatar
Bowen Wu committed
120
121
122
123
124
125
126
            
        return True

    def fuzz_once(self, mut_choice):
        mut = self.get_mutant(mut_choice)

        mps_prog = MPSProgram(**mut["mps"])
127
128
        idx = mut["id"] % OptFuzzer.MAX_MUTANTS_IN_DIR # prevent running our of inodes
        fname = os.path.join(self.save_path, "mutant_" + str(idx)+".mps")
Bowen Wu's avatar
Bowen Wu committed
129
130
131
        with open(fname, "w") as f:
            f.write(mps_prog.__str__())
        
Ambi's avatar
Ambi committed
132
        c_start = time.time()
Bowen Wu's avatar
Bowen Wu committed
133
        cplex_sol = self.cplex(fname)
Ambi's avatar
Ambi committed
134
135
136
        c_time = time.time() - c_start

        g_start = time.time()
Bowen Wu's avatar
Bowen Wu committed
137
        gurobi_sol = self.gurobi(fname)
Ambi's avatar
Ambi committed
138
        g_time = time.time() - g_start
Bowen Wu's avatar
Bowen Wu committed
139
140
141
142
143
144

        if cplex_sol is None or gurobi_sol is None:
            print("[Fatal] Cannot load the solution")
            self.checkpoint()
            os.abort()

Ambi's avatar
Ambi committed
145
146
147
148
149
150
151
        are_equal = self.sol_equal(cplex_sol, gurobi_sol)
        print_ind_stats = False
        if(print_ind_stats):
            #Id, Name, Equal, Cplex time, Gurobi time
            print('{},{},{},{},{}'.format(mut['id']-203, mut['seed_name'].replace('seed/',''), are_equal, c_time, g_time))

        if not are_equal:
Bowen Wu's avatar
Bowen Wu committed
152
153
154
155
156
157
158
159
160
161
            dfname = os.path.join(self.diff_path, f"diff_{len(self.diff)}.mps")
            with open(dfname, "w") as f:
                f.write(mps_prog.__str__())
            self.diff.append(mut)
        
        self.all_mutant.append(mut)

    def print_stats(self):
        print(f"Seeds: {self.seed}")
        print("Mutation methods used: ", self.mut_method)
Bowen Wu's avatar
Bowen Wu committed
162
        print("# Mutations: ", self.next_id - len(self.seed))
Bowen Wu's avatar
Bowen Wu committed
163
164
165
166
167
168
169
170
171
172
173
        print("# Mutants that caused a difference: ", len(self.diff))
    
    def checkpoint(self):
        # store all the mutants that have been generated to disks
        fname = os.path.join(self.checkpoint_path, f"ckpt_{self.next_id - 1}")
        with open(fname, "wb") as f:
            pickle.dump(self.all_mutant, f)
        self.all_mutant = []

    def save_states(self):
        self.checkpoint()
174
175
176
177
        if len(self.diff) > 0:
            fname = os.path.join(self.diff_path, "diff.pickle")
            with open(fname, "wb") as f:
                pickle.dump(self.diff, f)
Bowen Wu's avatar
Bowen Wu committed
178
179
180
181
182
183
184
185
186
187
188
189

    def fuzz(self, max_time, mut_choice = "fixed"):
        elapse = 0 # in seconds
        nround = 0
        while elapse < max_time:
            start = time.time()
            self.fuzz_once(mut_choice)
            elapse += time.time() - start
            if nround % self.checkpoint_freq == 0 and nround != 0:
                self.checkpoint()
            nround += 1
        self.print_stats()
190
191
        self.cplex.print_solver_stats()
        self.gurobi.print_solver_stats()
Bowen Wu's avatar
Bowen Wu committed
192
193
194
        self.save_states()

def main():
195
196
197
198
199
200
201
202
    from config import parser
    args = parser.parse_args()
    print(args)

    mut_method = []
    for m in args.mut_methods:
        c = None
        if m == "ScaleMut":
Ambi's avatar
Ambi committed
203
            c = ScaleMut(0.3,2.5)
204
205
206
207
208
209
        elif m == "SparseMatMut":
            c = SparseMatMut(0.5)
        elif m == "DenseMatMut":
            c = DenseMatMut(0.5)
        elif m == "FlipSignMut":
            c = FlipSignMut(0.5)
Ambi's avatar
Ambi committed
210
211
        elif m == "NoOpMut":
            c = NoOpMut()
212
213
214
215
216
        mut_method.append(c)

    import glob
    seed = glob.glob(os.path.join(args.seed_path, "*.mps"))
    
Bowen Wu's avatar
Bowen Wu committed
217
218
    cpx = CplexSolver()
    grb = GurobiSolver()
219
220
221
222
223
224
225
226
227
    
    ts = str(time.time())
    save_path = os.path.join(args.save_path, ts)
    checkpoint_freq = args.ckpt_freq
    checkpoint_path = os.path.join(args.ckpt_path, ts)
    diff_path = os.path.join(args.diff_path, ts)
    max_time = args.max_time
    mut_choice = args.mut_choice
    
Bowen Wu's avatar
Bowen Wu committed
228
229
230
231
232
    fuzzer = OptFuzzer(seed, mut_method, cpx, grb, save_path, checkpoint_freq, checkpoint_path, diff_path)
    fuzzer.fuzz(max_time, mut_choice)

if __name__ == "__main__":
    main()