From 32442ab0e9d10b0a8a6a89ae04a3fcd80729da77 Mon Sep 17 00:00:00 2001 From: weiyu Date: Thu, 10 Oct 2019 17:33:57 -0700 Subject: [PATCH] Design a method to select predicate branches based on exploration counts --- funcinst.cc | 6 +++--- funcinst.h | 2 +- funcnode.cc | 1 + history.cc | 2 +- newfuzzer.cc | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++-- newfuzzer.h | 1 + predicate.cc | 2 ++ predicate.h | 4 ++++ 8 files changed, 69 insertions(+), 7 deletions(-) diff --git a/funcinst.cc b/funcinst.cc index 4fcf0e7c..44bb167e 100644 --- a/funcinst.cc +++ b/funcinst.cc @@ -4,7 +4,7 @@ FuncInst::FuncInst(ModelAction *act, FuncNode *func_node) : single_location(true), execution_number(model->get_execution_number()), - marker(0) /* The marker for FuncNode starts from 1 */ + action_marker(0) /* The marker for FuncNode starts from 1 */ { ASSERT(act); ASSERT(func_node); @@ -50,12 +50,12 @@ bool FuncInst::add_succ(FuncInst * other) void FuncInst::set_associated_act(ModelAction * act, uint32_t marker) { associated_act = act; - this->marker = marker; + action_marker = marker; } ModelAction * FuncInst::get_associated_act(uint32_t marker) { - if (marker == this->marker) + if (action_marker == marker) return associated_act; else return NULL; diff --git a/funcinst.h b/funcinst.h index fe4adb48..98af6bcb 100644 --- a/funcinst.h +++ b/funcinst.h @@ -65,7 +65,7 @@ private: int execution_number; ModelAction * associated_act; - uint32_t marker; + uint32_t action_marker; /* Currently not in use. May remove this field later * diff --git a/funcnode.cc b/funcnode.cc index 05974d78..75cb0cb8 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -306,6 +306,7 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) inst_id_map.put(next_inst, inst_counter++); it = it->getNext(); + curr_pred->incr_count(); } } diff --git a/history.cc b/history.cc index 4fde9144..34ec0801 100644 --- a/history.cc +++ b/history.cc @@ -341,7 +341,7 @@ void ModelHistory::check_waiting_write(ModelAction * write_act) /* Check if the written value satisfies every predicate expression */ for (uint i = 0; i < concrete_exprs->size(); i++) { struct concrete_pred_expr concrete = (*concrete_exprs)[i]; - bool equality; + bool equality = false; switch (concrete.token) { case EQUALITY: equality = (value == concrete.value); diff --git a/newfuzzer.cc b/newfuzzer.cc index 4863d47c..e290db41 100644 --- a/newfuzzer.cc +++ b/newfuzzer.cc @@ -77,6 +77,7 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector * rf_set return -1; } else { Predicate * selected_branch = get_selected_child_branch(tid); +// selected_branch->incr_count(); failed_predicates.put(selected_branch, true); SnapVector * pruned_writes = thrd_pruned_writes[thread_id]; @@ -119,11 +120,16 @@ Predicate * NewFuzzer::selectBranch(thread_id_t tid, Predicate * curr_pred, Func ModelVector * children = curr_pred->get_children(); SnapVector branches; + uint32_t numerator = 1; for (uint i = 0; i < children->size(); i++) { Predicate * child = (*children)[i]; if (child->get_func_inst() == read_inst && !failed_predicates.contains(child)) { branches.push_back(child); + + // max of (exploration counts + 1) + if (child->get_count() + 1 > numerator) + numerator = child->get_count() + 1; } } @@ -134,13 +140,61 @@ Predicate * NewFuzzer::selectBranch(thread_id_t tid, Predicate * curr_pred, Func } // randomly select a branch - int random_index = random() % branches.size(); - Predicate * random_branch = branches[ random_index ]; + // int random_index = random() % branches.size(); + // Predicate * random_branch = branches[ random_index ]; + + int index = choose_index(&branches, numerator); + Predicate * random_branch = branches[ index ]; thrd_selected_child_branch[thread_id] = random_branch; return random_branch; } +/** + * @brief Select a branch from the given predicate branches based + * on their exploration counts. + * + * Let b_1, ..., b_n be branches with exploration counts c_1, ..., c_n + * M := max(c_1, ..., c_n) + 1 + * Factor f_i := M / (c_i + 1) + * The probability p_i that branch b_i is selected: + * p_i := f_i / (f_1 + ... + f_n) + * = \fraction{ 1/(c_i + 1) }{ 1/(c_1 + 1) + ... + 1/(c_n + 1) } + * + * Note: (1) c_i + 1 is used because counts may be 0. + * (2) The numerator of f_i is chosen to reduce the effect of underflow + * + * @param numerator is M defined above + */ +int NewFuzzer::choose_index(SnapVector * branches, uint32_t numerator) +{ + if (branches->size() == 1) + return 0; + + double total_factor = 0; + SnapVector factors = SnapVector( branches->size() ); + for (uint i = 0; i < branches->size(); i++) { + Predicate * branch = (*branches)[i]; + double factor = (double) numerator / (branch->get_count() + 1); + total_factor += factor; + factors[i] = factor; + } + + double prob = (double) random() / RAND_MAX; + double prob_sum = 0; + int index = 0; + + for (uint i = 0; i < factors.size(); i++) { + prob_sum += (double) factors[i] / total_factor; + if (prob_sum > prob) { + index = i; + break; + } + } + + return index; +} + Predicate * NewFuzzer::get_selected_child_branch(thread_id_t tid) { int thread_id = id_to_int(tid); diff --git a/newfuzzer.h b/newfuzzer.h index d1037a61..a4699bdd 100644 --- a/newfuzzer.h +++ b/newfuzzer.h @@ -35,6 +35,7 @@ private: bool prune_writes(thread_id_t tid, Predicate * pred, SnapVector * rf_set, inst_act_map_t * inst_act_map); Predicate * selectBranch(thread_id_t tid, Predicate * curr_pred, FuncInst * read_inst); + int choose_index(SnapVector * branches, uint32_t numerator); /* The set of Threads put to sleep by NewFuzzer because no writes in rf_set satisfies the selected predicate. Only used by selectWrite. */ diff --git a/predicate.cc b/predicate.cc index 9e2f1621..a64737e8 100644 --- a/predicate.cc +++ b/predicate.cc @@ -6,6 +6,7 @@ Predicate::Predicate(FuncInst * func_inst, bool is_entry) : func_inst(func_inst), entry_predicate(is_entry), does_write(false), + exploration_count(0), pred_expressions(16), children(), parent(NULL), @@ -129,6 +130,7 @@ void Predicate::print_predicate() if (does_write) { model_print("Does write\n"); } + model_print("Count: %d\n", exploration_count); model_print("\"];\n"); } diff --git a/predicate.h b/predicate.h index 4c26a9dd..b85eab0d 100644 --- a/predicate.h +++ b/predicate.h @@ -37,6 +37,9 @@ public: ConcretePredicate * evaluate(inst_act_map_t * inst_act_map, thread_id_t tid); + uint32_t get_count() { return exploration_count; } + void incr_count() { exploration_count++; } + void print_predicate(); void print_pred_subtree(); @@ -45,6 +48,7 @@ private: FuncInst * func_inst; bool entry_predicate; bool does_write; + uint32_t exploration_count; /* May have multiple predicate expressions */ PredExprSet pred_expressions; -- 2.34.1