linux-kernel - [PATCH 6/8] ktest/config-bisect: Try harder to find a new config

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Sun, 16 Jul 2017 19:16:28 -0500
From:   Scott Wood <swood@...hat.com>
To:     Steven Rostedt <rostedt@...dmis.org>
Cc:     linux-kernel@...r.kernel.org, Scott Wood <swood@...hat.com>
Subject: [PATCH 6/8] ktest/config-bisect: Try harder to find a new config

From: Scott Wood <oss@...error.net>

It's possible that the arbitrarily chosen half of the config differences
fails to make any actual difference in the output config, due to options
that are present in .config but not independently changeable (e.g. the
mutually-exclusive symbols of a "choice" kconfig construct, or a symbol
that has been "select"ed by another).

Try harder to generate a new and different config by randomizing the key
order and bisection percentage, and repeating a few times.

Explicitly randomizing also makes it possible to skip a broken generated
config by simply calling the script again, even on older versions of Perl
that didn't automatically randomize hash order.

Signed-off-by: Scott Wood <swood@...hat.com>
---
 tools/testing/ktest/config-bisect.pl | 41 +++++++++++++++++++++---------------
 1 file changed, 24 insertions(+), 17 deletions(-)

diff --git a/tools/testing/ktest/config-bisect.pl b/tools/testing/ktest/config-bisect.pl
index 63a3a940b5de..54f27b45079f 100755
--- a/tools/testing/ktest/config-bisect.pl
+++ b/tools/testing/ktest/config-bisect.pl
@@ -5,6 +5,7 @@
 #
 
 use strict;
+use List::Util qw(shuffle);
 
 my $outputdir;
 
@@ -153,9 +154,11 @@ sub run_config_bisect {
 	my @diff_arr = diff_config_vals \%good_configs, \%bad_configs;
 	my $len_diff = $#diff_arr + 1;
 
-	my $runtest = 1;
+	my $rand_tries = 10;
+	my $runtest = 0;
 	my %new_configs;
 	my $ret;
+	my $count = 0;
 
 	print "d=$len_diff\n";
 
@@ -164,33 +167,37 @@ sub run_config_bisect {
 		exit 2;
 	}
 
-	my %tmp_config = %bad_configs;
-
-	my $half = int($#diff_arr / 2);
-	my @tophalf = @diff_arr[0 .. $half];
-
-	print "Settings bisect with top half:\n";
-	foreach my $item (@tophalf) {
-		$tmp_config{$item} = $good_configs{$item};
-	}
+	while ($runtest == 0 && ++$count <= $rand_tries) {
+		my %tmp_config = %bad_configs;
 
-	$runtest = process_new_config \%tmp_config, \%new_configs,
-		\%good_configs, \%bad_configs, $outfile;
+		# If we fail to generate a new config (due to the top half
+		# configs being unchangeable without the bottom half configs)
+		# then try a few random permutations, and if those fail try
+		# each option one at a time.
 
-	if (!$runtest) {
-		my %tmp_config = %bad_configs;
+		if ($count <= $rand_tries) {
+			@diff_arr = shuffle(@diff_arr);
+		}
 
-		print "Try bottom half\n";
+		my $half = int($#diff_arr / 2);
+		if ($count > 2) {
+			$half = int(rand($#diff_arr));
+		}
 
-		my @bottomhalf = @diff_arr[$half+1 .. $#diff_arr];
+		my @tophalf = @diff_arr[0 .. $half];
 
-		foreach my $item (@bottomhalf) {
+		foreach my $item (@tophalf) {
 			$tmp_config{$item} = $good_configs{$item};
 		}
 
 		$runtest = process_new_config \%tmp_config, \%new_configs,
 				\%good_configs, \%bad_configs, $outfile;
 	}
+
+	if ($runtest == 0) {
+		print "$0: No more bisecting possible\n";
+		exit 2;
+	}
 }
 
 sub cb_by_file {
-- 
2.9.4