executor, ipc: modify the IO between KCOV<->executor<->fuzzer

Now executor is able to read comparisons data from KCOV and write them
to fuzzer.

3 files changed, 255 insertions, 43 deletions

diff --git a/executor/executor.cc b/executor/executor.cc
index fdd44e246..8f5e221ac 100644
--- a/executor/executor.cc
+++ b/executor/executor.cc
@@ -106,6 +106,75 @@ struct res_t {
 
 res_t results[kMaxCommands];
 
+enum {
+	KCOV_CMP_CONST = 1,
+	KCOV_CMP_SIZE1 = 0,
+	KCOV_CMP_SIZE2 = 2,
+	KCOV_CMP_SIZE4 = 4,
+	KCOV_CMP_SIZE8 = 6,
+	KCOV_CMP_SIZE_MASK = 6,
+};
+
+struct kcov_comparison_t {
+	uint64_t type;
+	uint64_t arg1;
+	uint64_t arg2;
+
+	bool operator==(const struct kcov_comparison_t& other) const
+	{
+		return type == other.type && arg1 == other.arg1 && arg2 == other.arg2;
+	}
+
+	bool operator<(const struct kcov_comparison_t& other) const
+	{
+		if (type != other.type)
+			return type < other.type;
+		if (arg1 != other.arg1)
+			return arg1 < other.arg1;
+		return arg2 < other.arg2;
+	}
+
+	// Writes the structure using the write_one function for each field.
+	// Inspired by write_output() function.
+	void write(uint32_t* (*write_one)(uint32_t))
+	{
+		// Write order: type arg1 arg2.
+		write_one((uint32_t)type);
+
+		// KCOV converts all arguments of size x first to uintx_t and then to
+		// uint64_t. We want to properly extend signed values, e.g we want
+		// int8_t c = 0xfe to be represented as 0xfffffffffffffffe.
+		// Note that uint8_t c = 0xfe will be represented the same way.
+		// This is ok because during hints processing we will anyways try
+		// the value 0x00000000000000fe.
+		switch (type & KCOV_CMP_SIZE_MASK) {
+		case KCOV_CMP_SIZE1:
+			arg1 = (uint64_t)(int64_t)(int8_t)arg1;
+			arg2 = (uint64_t)(int64_t)(int8_t)arg2;
+			break;
+		case KCOV_CMP_SIZE2:
+			arg1 = (uint64_t)(int64_t)(int16_t)arg1;
+			arg2 = (uint64_t)(int64_t)(int16_t)arg2;
+			break;
+		case KCOV_CMP_SIZE4:
+			arg1 = (uint64_t)(int64_t)(int32_t)arg1;
+			arg2 = (uint64_t)(int64_t)(int32_t)arg2;
+			break;
+		}
+		bool is_size_8 = (type & KCOV_CMP_SIZE_MASK) == KCOV_CMP_SIZE8;
+		if (!is_size_8) {
+			write_one((uint32_t)arg1);
+			write_one((uint32_t)arg2);
+			return;
+		}
+		// If we have 64 bits arguments then write them in Little-endian.
+		write_one((uint32_t)(arg1 & 0xFFFFFFFF));
+		write_one((uint32_t)(arg1 >> 32));
+		write_one((uint32_t)(arg2 & 0xFFFFFFFF));
+		write_one((uint32_t)(arg2 >> 32));
+	}
+};
+
 struct thread_t {
 	bool created;
 	int id;
@@ -599,46 +668,56 @@ void handle_completion(thread_t* th)
 		write_output(th->fault_injected);
 		uint32_t* signal_count_pos = write_output(0); // filled in later
 		uint32_t* cover_count_pos = write_output(0); // filled in later
-
-		// Write out feedback signals.
-		// Currently it is code edges computed as xor of two subsequent basic block PCs.
-		uint64_t* cover_data = th->cover_data + 1;
-		uint32_t cover_size = th->cover_size;
-		uint32_t prev = 0;
-		uint32_t nsig = 0;
-		for (uint32_t i = 0; i < cover_size; i++) {
-			uint32_t pc = cover_data[i];
-			uint32_t sig = pc ^ prev;
-			prev = hash(pc);
-			if (dedup(sig))
-				continue;
-			write_output(sig);
-			nsig++;
-		}
-		*signal_count_pos = nsig;
-		if (flag_collect_cover) {
-			// Write out real coverage (basic block PCs).
-			if (flag_dedup_cover) {
-				std::sort(cover_data, cover_data + cover_size);
-				uint64_t w = 0;
-				uint64_t last = 0;
-				for (uint32_t i = 0; i < cover_size; i++) {
-					uint64_t pc = cover_data[i];
-					if (pc == last)
-						continue;
-					cover_data[w++] = last = pc;
+		uint32_t* comps_count_pos = write_output(0); // filled in later
+		uint32_t nsig = 0, cover_size = 0, comps_size = 0;
+
+		if (flag_collect_comps) {
+			// Collect only the comparisons
+			comps_size = th->cover_size;
+			kcov_comparison_t* start = (kcov_comparison_t*)th->cover_data;
+			kcov_comparison_t* end = start + comps_size;
+			std::sort(start, end);
+			comps_size = std::unique(start, end) - start;
+			for (uint32_t i = 0; i < comps_size; ++i)
+				start[i].write(write_output);
+		} else {
+			// Write out feedback signals.
+			// Currently it is code edges computed as xor of
+			// two subsequent basic block PCs.
+			uint32_t prev = 0;
+			for (uint32_t i = 0; i < th->cover_size; i++) {
+				uint32_t pc = (uint32_t)th->cover_data[i];
+				uint32_t sig = pc ^ prev;
+				prev = hash(pc);
+				if (dedup(sig))
+					continue;
+				write_output(sig);
+				nsig++;
+			}
+			if (flag_collect_cover) {
+				// Write out real coverage (basic block PCs).
+				cover_size = th->cover_size;
+				if (flag_dedup_cover) {
+					uint64_t* start = (uint64_t*)th->cover_data;
+					uint64_t* end = start + cover_size;
+					std::sort(start, end);
+					cover_size = std::unique(start, end) - start;
 				}
-				cover_size = w;
+				// Truncate PCs to uint32_t assuming that they fit into 32-bits.
+				// True for x86_64 and arm64 without KASLR.
+				for (uint32_t i = 0; i < cover_size; i++)
+					write_output((uint32_t)th->cover_data[i]);
 			}
-			// Truncate PCs to uint32_t assuming that they fit into 32-bits.
-			// True for x86_64 and arm64 without KASLR.
-			for (uint32_t i = 0; i < cover_size; i++)
-				write_output((uint32_t)cover_data[i]);
-			*cover_count_pos = cover_size;
 		}
-		debug("out #%u: index=%u num=%u errno=%d sig=%u cover=%u\n",
-		      completed, th->call_index, th->call_num, reserrno, nsig, cover_size);
-
+		// Write out real coverage (basic block PCs).
+		*cover_count_pos = cover_size;
+		// Write out number of comparisons
+		*comps_count_pos = comps_size;
+		// Write out number of signals
+		*signal_count_pos = nsig;
+		debug("out #%u: index=%u num=%u errno=%d sig=%u cover=%u comps=%u\n",
+		      completed, th->call_index, th->call_num, reserrno, nsig,
+		      cover_size, comps_size);
 		completed++;
 		__atomic_store_n(output_data, completed, __ATOMIC_RELEASE);
 	}
diff --git a/pkg/ipc/ipc.go b/pkg/ipc/ipc.go
index 674596d60..af0173c2e 100644
--- a/pkg/ipc/ipc.go
+++ b/pkg/ipc/ipc.go
@@ -64,6 +64,11 @@ const (
 	statusFail  = 67
 	statusError = 68
 	statusRetry = 69
+
+	// Comparison types masks taken from KCOV headers.
+	compSizeMask  = 6
+	compSize8     = 6
+	compConstMask = 1
 )
 
 var (
@@ -222,10 +227,19 @@ type CallInfo struct {
 	Signal []uint32 // feedback signal, filled if FlagSignal is set
 	Cover  []uint32 // per-call coverage, filled if FlagSignal is set and cover == true,
 	//if dedup == false, then cov effectively contains a trace, otherwise duplicates are removed
-	Errno         int // call errno (0 if the call was successful)
+	Comps         prog.CompMap // per-call comparison operands
+	Errno         int          // call errno (0 if the call was successful)
 	FaultInjected bool
 }
 
+func GetCompMaps(info []CallInfo) []prog.CompMap {
+	compMaps := make([]prog.CompMap, len(info))
+	for i, inf := range info {
+		compMaps[i] = inf.Comps
+	}
+	return compMaps
+}
+
 // Exec starts executor binary to execute program p and returns information about the execution:
 // output: process output
 // info: per-call info
@@ -264,7 +278,8 @@ func (env *Env) Exec(opts *ExecOpts, p *prog.Prog) (output []byte, info []CallIn
 		return
 	}
 
-	if env.config.Flags&FlagSignal == 0 || p == nil {
+	if p == nil || env.config.Flags&FlagSignal == 0 &&
+		env.config.Flags&FlagCollectComps == 0 {
 		return
 	}
 	info, err0 = env.readOutCoverage(p)
@@ -282,9 +297,27 @@ func (env *Env) readOutCoverage(p *prog.Prog) (info []CallInfo, err0 error) {
 		return true
 	}
 
+	readOutAndSetErr := func(v *uint32, msg string, args ...interface{}) bool {
+		if !readOut(v) {
+			err0 = fmt.Errorf(msg, args)
+			return false
+		}
+		return true
+	}
+
+	// Reads out a 64 bits int in Little-endian as two blocks of 32 bits.
+	readOut64 := func(v *uint64, msg string, args ...interface{}) bool {
+		var a, b uint32
+		if !(readOutAndSetErr(&a, msg, args) && readOutAndSetErr(&b, msg, args)) {
+			return false
+		}
+		*v = uint64(a) + uint64(b)<<32
+		return true
+	}
+
 	var ncmd uint32
-	if !readOut(&ncmd) {
-		err0 = fmt.Errorf("executor %v: failed to read output coverage", env.pid)
+	if !readOutAndSetErr(&ncmd,
+		"executor %v: failed to read output coverage", env.pid) {
 		return
 	}
 	info = make([]CallInfo, len(p.Calls))
@@ -303,8 +336,8 @@ func (env *Env) readOutCoverage(p *prog.Prog) (info []CallInfo, err0 error) {
 		return buf.String()
 	}
 	for i := uint32(0); i < ncmd; i++ {
-		var callIndex, callNum, errno, faultInjected, signalSize, coverSize uint32
-		if !readOut(&callIndex) || !readOut(&callNum) || !readOut(&errno) || !readOut(&faultInjected) || !readOut(&signalSize) || !readOut(&coverSize) {
+		var callIndex, callNum, errno, faultInjected, signalSize, coverSize, compsSize uint32
+		if !readOut(&callIndex) || !readOut(&callNum) || !readOut(&errno) || !readOut(&faultInjected) || !readOut(&signalSize) || !readOut(&coverSize) || !readOut(&compsSize) {
 			err0 = fmt.Errorf("executor %v: failed to read output coverage", env.pid)
 			return
 		}
@@ -331,8 +364,10 @@ func (env *Env) readOutCoverage(p *prog.Prog) (info []CallInfo, err0 error) {
 				env.pid, i, callIndex, signalSize, coverSize)
 			return
 		}
+		// Read out signals.
 		info[callIndex].Signal = out[:signalSize:signalSize]
 		out = out[signalSize:]
+		// Read out coverage.
 		if coverSize > uint32(len(out)) {
 			err0 = fmt.Errorf("executor %v: failed to read output coverage: record %v, call %v, signalsize=%v coversize=%v",
 				env.pid, i, callIndex, signalSize, coverSize)
@@ -340,6 +375,54 @@ func (env *Env) readOutCoverage(p *prog.Prog) (info []CallInfo, err0 error) {
 		}
 		info[callIndex].Cover = out[:coverSize:coverSize]
 		out = out[coverSize:]
+		// Read out comparisons.
+		compMap := make(prog.CompMap)
+		for j := uint32(0); j < compsSize; j++ {
+			var typ uint32
+			var op1, op2 uint64
+			if !readOutAndSetErr(&typ,
+				"executor %v: failed while reading type of comparison %v", env.pid, j) {
+				return
+			}
+			if typ > compConstMask|compSizeMask {
+				err0 = fmt.Errorf("executor %v: got wrong value (%v) while reading type of comparison %v",
+					env.pid, typ, j)
+				return
+			}
+
+			isSize8 := (typ & compSizeMask) == compSize8
+			isConst := (typ & compConstMask) != 0
+			arg1ErrString := "executor %v: failed while reading op1 of comparison %v"
+			arg2ErrString := "executor %v: failed while reading op2 of comparison %v"
+			if isSize8 {
+				var tmp1, tmp2 uint32
+				if !readOutAndSetErr(&tmp1, arg1ErrString, env.pid, j) ||
+					!readOutAndSetErr(&tmp2, arg2ErrString, env.pid, j) {
+					return
+				}
+				op1 = uint64(tmp1)
+				op2 = uint64(tmp2)
+			} else {
+				if !readOut64(&op1, arg1ErrString, env.pid, j) ||
+					!readOut64(&op2, arg2ErrString, env.pid, j) {
+					return
+				}
+			}
+			if op1 == op2 {
+				// It's useless to store such comparisons.
+				continue
+			}
+			compMap.AddComp(op2, op1)
+			if isConst {
+				// If one of the operands was const, then this operand is always
+				// placed first in the instrumented callbacks. Such an operand
+				// could not be an argument of our syscalls (because otherwise
+				// it wouldn't be const), thus we simply ignore it.
+				continue
+			}
+			compMap.AddComp(op1, op2)
+		}
+		info[callIndex].Comps = compMap
 	}
 	return
 }
diff --git a/prog/hints.go b/prog/hints.go
new file mode 100644
index 000000000..50efc6b8a
--- /dev/null
+++ b/prog/hints.go
@@ -0,0 +1,50 @@
+// Copyright 2017 syzkaller project authors. All rights reserved.
+// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
+
+package prog
+
+// A hint is basically a tuple consisting of a pointer to an argument
+// in one of the syscalls of a program and a value, which should be
+// assigned to that argument (we call it a replacer).
+
+// A simplified version of hints workflow looks like this:
+//		1. Fuzzer launches a program (we call it a hint seed) and collects all
+// the comparisons' data for every syscall in the program.
+//		2. Next it tries to match the obtained comparison operands' values
+// vs. the input arguments' values.
+//		3. For every such match the fuzzer mutates the program by
+// replacing the pointed argument with the saved value.
+//		4. If a valid program is obtained, then fuzzer launches it and
+// checks if new coverage is obtained.
+// For more insights on particular mutations please see prog/hints_test.go.
+
+type uint64Set map[uint64]bool
+
+// Example: for comparisons {(op1, op2), (op1, op3), (op1, op4), (op2, op1)}
+// this map will store the following:
+// m = {
+//		op1: {map[op2]: true, map[op3]: true, map[op4]: true},
+//		op2: {map[op1]: true}
+// }.
+type CompMap map[uint64]uint64Set
+
+var specialIntsSet uint64Set
+
+func (m CompMap) AddComp(arg1, arg2 uint64) {
+	if _, ok := specialIntsSet[arg2]; ok {
+		// We don't want to add arg2 because it's in the set of
+		// "special" values, which the fuzzer will try anyways.
+		return
+	}
+	if _, ok := m[arg1]; !ok {
+		m[arg1] = make(uint64Set)
+	}
+	m[arg1][arg2] = true
+}
+
+func init() {
+	specialIntsSet = make(uint64Set)
+	for _, v := range specialInts {
+		specialIntsSet[v] = true
+	}
+}