opt_fuzz.py 9.81 KB
Newer Older
Bowen Wu's avatar
Bowen Wu committed
1
2
3
4
5
import time
import random
import os
import math
import pickle
Bowen Wu's avatar
Bowen Wu committed
6
import heapq
7
from copy import deepcopy
Bowen Wu's avatar
Bowen Wu committed
8

Bowen Wu's avatar
Bowen Wu committed
9
from typing import List, Tuple
Bowen Wu's avatar
Bowen Wu committed
10
11
12
from queue import Queue

from generator import MPSProgram
13
from mps_mut import DenseMatMut, FlipObjSense, ScaleMut, SparseMatMut, FlipSignMut, NoOpMut, MoreIntMut
Bowen Wu's avatar
Bowen Wu committed
14
15
16
17
18
19
20
21
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):
22
    MAX_MUTANTS_IN_DIR = 10
23
24
25
26
27
28
29
30
31
    def __init__(self, seed : List, 
                 mut_method : List, 
                 cplex : CplexSolver, 
                 gurobi : GurobiSolver, 
                 save_path : str, 
                 checkpoint_freq : int, 
                 checkpoint_path : str, 
                 diff_path: str, 
                 abs_tol = 1e-6) -> None:
Bowen Wu's avatar
Bowen Wu committed
32
33
        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
34
        self.no_op_mut_method = NoOpMut()
Bowen Wu's avatar
Bowen Wu committed
35
36
37
38
39
40
41
42
43
44
45
        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
46
        self.abs_tol = abs_tol
Bowen Wu's avatar
Bowen Wu committed
47
48
        self.diff = [] # mutants that cause differences
        self.all_mutant = []
Bowen Wu's avatar
Bowen Wu committed
49
50
        # self.queue = Queue(maxsize=0) # unbounded queue for seeds
        self.queue = []
Bowen Wu's avatar
Bowen Wu committed
51
        self.next_id = 0 # id assigned to the next mutant
Ambi's avatar
Ambi committed
52
        print("Initializing seeds")
Bowen Wu's avatar
Bowen Wu committed
53
54
55
        for s in self.seed:
            mutant = {
                "id" : self.next_id,
Bowen Wu's avatar
Bowen Wu committed
56
                "root" : self.next_id,
Bowen Wu's avatar
Bowen Wu committed
57
58
                "parent" : [-1], # root seed, no parent
                "mut_method" : "",
Bowen Wu's avatar
Bowen Wu committed
59
                "mps" : load_mps_dict(s)
Bowen Wu's avatar
Bowen Wu committed
60
            }
Bowen Wu's avatar
Bowen Wu committed
61
            heapq.heappush(self.queue, ((-1, self.next_id, 1), mutant))
Bowen Wu's avatar
Bowen Wu committed
62
            self.next_id += 1
Bowen Wu's avatar
Bowen Wu committed
63
            # self.queue.put_nowait(mutant)
Bowen Wu's avatar
Bowen Wu committed
64
        self.mut_cnt_per_seed = [0] * len(self.seed)
Ambi's avatar
Ambi committed
65
        print("Seeds initialized")
Bowen Wu's avatar
Bowen Wu committed
66

Bowen Wu's avatar
Bowen Wu committed
67
68
69
70
    def get_mutant(self, mut_choice : str, nr_mutations: int = 3) -> Tuple[dict, dict]:
        # parent = self.queue.get()
        parent_ent = heapq.heappop(self.queue)
        parent = parent_ent[1]
Bowen Wu's avatar
Bowen Wu committed
71
        # print(parent_ent[0])
Bowen Wu's avatar
Bowen Wu committed
72
        self.mut_cnt_per_seed[parent["root"]] += 1
Bowen Wu's avatar
Bowen Wu committed
73

74
        mps = deepcopy(parent["mps"])
Bowen Wu's avatar
Bowen Wu committed
75
76
77
78
79
80
81
82
83
84
85
86
87
        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
88
        #print("========== GOING TO MUTATE ============")
Ambi's avatar
Ambi committed
89
90
91
92
93
        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]
Bowen Wu's avatar
Bowen Wu committed
94
95
                # print(self.mut_method)
                # print('idx = ', idx, ' Mutating using ', mut_method)
Ambi's avatar
Ambi committed
96
97
98
                mps_prime = mut_method(mps_prime)
        else:
            mps_prime = self.mut_method[idx](mps)
Bowen Wu's avatar
Bowen Wu committed
99
        
Bowen Wu's avatar
Bowen Wu committed
100
101
102
103
        ret = {
            "id" : self.next_id,
            "parent" : [parent["id"]], # root seed, no parent
            "mut_method" : self.mut_method[idx].__str__(),
Bowen Wu's avatar
Bowen Wu committed
104
105
106
            "mps" : mps_prime,
            "root" : parent["root"],
            "mut_no" : self.mut_cnt_per_seed[parent["root"]]
Bowen Wu's avatar
Bowen Wu committed
107
108
109
110
        }

        self.next_id += 1

Bowen Wu's avatar
Bowen Wu committed
111
112
        # self.queue.put(parent)
        # heapq.heappush(self.queue, parent_ent)
Bowen Wu's avatar
Bowen Wu committed
113

Bowen Wu's avatar
Bowen Wu committed
114
        return parent_ent, ret
Bowen Wu's avatar
Bowen Wu committed
115
    
116
    def sol_equal(self, sol1 : dict, sol2 : dict, check_var = False) -> bool:
Bowen Wu's avatar
Bowen Wu committed
117
118
119
120
121
        if sol1['status'] != sol2['status']:
            return False
        
        if sol1['status'] == OPTIMAL:
            # check if the obj value is the same
Ambi's avatar
Ambi committed
122
            if not math.isclose(sol1['obj_val'], sol2['obj_val'], abs_tol=self.abs_tol):
Bowen Wu's avatar
Bowen Wu committed
123
124
125
                return False
            
            # check if the variable values are the same
126
127
128
129
130
131
            # 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
132
                    var2 = 0
133
134
135
136
137
                    try:
                        var2 = sol2['var_val'][v1]
                    except KeyError:
                        var2 = 0
                    
Ambi's avatar
Ambi committed
138
                    if not math.isclose(var1, var2, abs_tol=self.abs_tol):
139
                        return False
Bowen Wu's avatar
Bowen Wu committed
140
141
142
            
        return True

Bowen Wu's avatar
Bowen Wu committed
143
144
145
146
147
148
    def get_scaled_time_diff(self, time1, time2) -> float:
        return math.fabs(time1-time2) / max(time1, time2)

    def get_perturbed_time_diff(self, time) -> float:
        return min(1, time + random.uniform(-time,time) * 0.5)

Bowen Wu's avatar
Bowen Wu committed
149
    def fuzz_once(self, mut_choice):
Bowen Wu's avatar
Bowen Wu committed
150
        p, mut = self.get_mutant(mut_choice)
Bowen Wu's avatar
Bowen Wu committed
151
152

        mps_prog = MPSProgram(**mut["mps"])
153
154
        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
155
156
157
        with open(fname, "w") as f:
            f.write(mps_prog.__str__())
        
Ambi's avatar
Ambi committed
158
        c_start = time.time()
Bowen Wu's avatar
Bowen Wu committed
159
        cplex_sol = self.cplex(fname)
Ambi's avatar
Ambi committed
160
161
162
        c_time = time.time() - c_start

        g_start = time.time()
Bowen Wu's avatar
Bowen Wu committed
163
        gurobi_sol = self.gurobi(fname)
Ambi's avatar
Ambi committed
164
        g_time = time.time() - g_start
Bowen Wu's avatar
Bowen Wu committed
165
166
167
168
169
170

        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
171
        are_equal = self.sol_equal(cplex_sol, gurobi_sol)
Bowen Wu's avatar
Bowen Wu committed
172
173
        
        scaled_time_diff = self.get_scaled_time_diff(c_time, g_time)
Bowen Wu's avatar
Bowen Wu committed
174
175
176
        new_key = scaled_time_diff * 0.5 + math.fabs(scaled_time_diff - p[0][2]) * 0.5
        new_key = self.get_perturbed_time_diff(new_key)
        heapq.heappush(self.queue, ((-new_key, p[1]["id"], scaled_time_diff), p[1]))
Bowen Wu's avatar
Bowen Wu committed
177
178
        # print("time-diff = ", self.get_perturbed_time_diff(scaled_time_diff))
        
Ambi's avatar
Ambi committed
179
        if not are_equal:
Bowen Wu's avatar
Bowen Wu committed
180
181
182
183
            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)
Bowen Wu's avatar
Bowen Wu committed
184
185
186
187
188
189

        # 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,scaled_time_diff))

Bowen Wu's avatar
Bowen Wu committed
190
191
192
193
194
195
        
        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
196
        print("# Mutations: ", self.next_id - len(self.seed))
Bowen Wu's avatar
Bowen Wu committed
197
        print("# Mutants that caused a difference: ", len(self.diff))
Bowen Wu's avatar
Bowen Wu committed
198
199
200
201
        for i, s in enumerate(self.seed):
            print(i, " ", s, "\t", self.mut_cnt_per_seed[i])
        for i, d in enumerate(self.diff):
            print("Difference ", i, " is derived from ", d["root"], " at round ", d["mut_no"])
Bowen Wu's avatar
Bowen Wu committed
202
203
204
205
206
207
208
209
210
211
    
    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()
212
213
214
215
        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
216
217
218
219
220
221
222
223
224
225
226
227

    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()
228
229
        self.cplex.print_solver_stats()
        self.gurobi.print_solver_stats()
Bowen Wu's avatar
Bowen Wu committed
230
231
232
        self.save_states()

def main():
233
234
235
236
237
238
239
240
    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
241
            c = ScaleMut(0.3,2.5)
242
243
244
245
246
247
        elif m == "SparseMatMut":
            c = SparseMatMut(0.5)
        elif m == "DenseMatMut":
            c = DenseMatMut(0.5)
        elif m == "FlipSignMut":
            c = FlipSignMut(0.5)
248
249
250
251
        elif m == "MoreIntMut":
            c = MoreIntMut(0.3)
        elif m == "FlipObjSense":
            c = FlipObjSense()
Ambi's avatar
Ambi committed
252
253
        elif m == "NoOpMut":
            c = NoOpMut()
254
255
256
257
258
        mut_method.append(c)

    import glob
    seed = glob.glob(os.path.join(args.seed_path, "*.mps"))
    
Bowen Wu's avatar
Bowen Wu committed
259
260
    cpx = CplexSolver()
    grb = GurobiSolver()
261
262
    
    ts = str(time.time())
Bowen Wu's avatar
Bowen Wu committed
263
    print("Timestamp = ", ts)
264
265
266
267
268
269
270
    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
271
272
273
274
275
    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()