Now we use a one-time scan and remove strategy in the remval minimizer,
which is not suitable for timing dependent instructions.

For example, instruction A will indicate an address where the config
chunk locates, and instruction B will make the configuration active. If
we have the following instruction sequence:

...
A1
B1
A2
B2
...

A2 and B2 are the actual instructions that trigger the bug.

If we scan from top to bottom, after we remove A1, the behavior of B1
might be unknowable, including not to crash the program. But we will
successfully remove B1 later cause A2 and B2 will crash the process
anyway:

...
A1
A2
B2
...

Now one more trimming will remove A1.

In the perfect case, we would need to be able to remove A and B (or C!) at
the same time. But for now, let's just add a loop around the minimizer.

Since we only remove instructions, this iterative algorithm is converging.

Tested with Bug 1908062.

Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 41 +++++++++++++++---------
 1 file changed, 26 insertions(+), 15 deletions(-)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
index 1a26bf5b93..378a7ccec6 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -71,21 +71,9 @@ def check_if_trace_crashes(trace, path):
     return False
 
 
-def minimize_trace(inpath, outpath):
-    global TIMEOUT
-    with open(inpath) as f:
-        trace = f.readlines()
-    start = time.time()
-    if not check_if_trace_crashes(trace, outpath):
-        sys.exit("The input qtest trace didn't cause a crash...")
-    end = time.time()
-    print("Crashed in {} seconds".format(end-start))
-    TIMEOUT = (end-start)*5
-    print("Setting the timeout for {} seconds".format(TIMEOUT))
-
-    i = 0
-    newtrace = trace[:]
+def remove_minimizer(newtrace, outpath):
     remove_step = 1
+    i = 0
     while i < len(newtrace):
         # 1.) Try to remove lines completely and reproduce the crash.
         # If it works, we're done.
@@ -174,7 +162,30 @@ def minimize_trace(inpath, outpath):
                     newtrace[i] = prior[0]
                     del newtrace[i+1]
         i += 1
-    check_if_trace_crashes(newtrace, outpath)
+
+
+def minimize_trace(inpath, outpath):
+    global TIMEOUT
+    with open(inpath) as f:
+        trace = f.readlines()
+    start = time.time()
+    if not check_if_trace_crashes(trace, outpath):
+        sys.exit("The input qtest trace didn't cause a crash...")
+    end = time.time()
+    print("Crashed in {} seconds".format(end-start))
+    TIMEOUT = (end-start)*5
+    print("Setting the timeout for {} seconds".format(TIMEOUT))
+
+    newtrace = trace[:]
+
+    # remove minimizer
+    old_len = len(newtrace) + 1
+    while(old_len > len(newtrace)):
+        old_len = len(newtrace)
+        remove_minimizer(newtrace, outpath)
+        newtrace = list(filter(lambda s: s != "", newtrace))
+
+    assert(check_if_trace_crashes(newtrace, outpath))
 
 
 if __name__ == '__main__':
-- 
2.25.1

On 201229 1240, Qiuhao Li wrote:
> Now we use a one-time scan and remove strategy in the remval minimizer,
> which is not suitable for timing dependent instructions.
> 
> For example, instruction A will indicate an address where the config
> chunk locates, and instruction B will make the configuration active. If
> we have the following instruction sequence:
> 
> ...
> A1
> B1
> A2
> B2
> ...
> 
> A2 and B2 are the actual instructions that trigger the bug.
> 
> If we scan from top to bottom, after we remove A1, the behavior of B1
> might be unknowable, including not to crash the program. But we will
> successfully remove B1 later cause A2 and B2 will crash the process
> anyway:
> 
> ...
> A1
> A2
> B2
> ...
> 
> Now one more trimming will remove A1.
> 
> In the perfect case, we would need to be able to remove A and B (or C!) at
> the same time. But for now, let's just add a loop around the minimizer.
> 
> Since we only remove instructions, this iterative algorithm is converging.
> 
> Tested with Bug 1908062.
> 
> Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>

Small note below, but otherwise:
Reviewed-by: Alexander Bulekov <alxndr@bu.edu>

> ---
>  scripts/oss-fuzz/minimize_qtest_trace.py | 41 +++++++++++++++---------
>  1 file changed, 26 insertions(+), 15 deletions(-)
> 
> diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
> index 1a26bf5b93..378a7ccec6 100755
> --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> @@ -71,21 +71,9 @@ def check_if_trace_crashes(trace, path):
>      return False
>  
>  
> -def minimize_trace(inpath, outpath):
> -    global TIMEOUT
> -    with open(inpath) as f:
> -        trace = f.readlines()
> -    start = time.time()
> -    if not check_if_trace_crashes(trace, outpath):
> -        sys.exit("The input qtest trace didn't cause a crash...")
> -    end = time.time()
> -    print("Crashed in {} seconds".format(end-start))
> -    TIMEOUT = (end-start)*5
> -    print("Setting the timeout for {} seconds".format(TIMEOUT))
> -
> -    i = 0
> -    newtrace = trace[:]
> +def remove_minimizer(newtrace, outpath):

Maybe a different name for this function?
e.g. minimize_each_line or minimize_iter

-Alex

>      remove_step = 1
> +    i = 0
>      while i < len(newtrace):
>          # 1.) Try to remove lines completely and reproduce the crash.
>          # If it works, we're done.
> @@ -174,7 +162,30 @@ def minimize_trace(inpath, outpath):
>                      newtrace[i] = prior[0]
>                      del newtrace[i+1]
>          i += 1
> -    check_if_trace_crashes(newtrace, outpath)
> +
> +
> +def minimize_trace(inpath, outpath):
> +    global TIMEOUT
> +    with open(inpath) as f:
> +        trace = f.readlines()
> +    start = time.time()
> +    if not check_if_trace_crashes(trace, outpath):
> +        sys.exit("The input qtest trace didn't cause a crash...")
> +    end = time.time()
> +    print("Crashed in {} seconds".format(end-start))
> +    TIMEOUT = (end-start)*5
> +    print("Setting the timeout for {} seconds".format(TIMEOUT))
> +
> +    newtrace = trace[:]
> +
> +    # remove minimizer
> +    old_len = len(newtrace) + 1
> +    while(old_len > len(newtrace)):
> +        old_len = len(newtrace)
> +        remove_minimizer(newtrace, outpath)
> +        newtrace = list(filter(lambda s: s != "", newtrace))
> +
> +    assert(check_if_trace_crashes(newtrace, outpath))
>  
>  
>  if __name__ == '__main__':
> -- 
> 2.25.1
> 

On Wed, 2021-01-06 at 23:53 -0500, Alexander Bulekov wrote:
> On 201229 1240, Qiuhao Li wrote:
> > Now we use a one-time scan and remove strategy in the remval
> > minimizer,
> > which is not suitable for timing dependent instructions.
> > 
> > For example, instruction A will indicate an address where the
> > config
> > chunk locates, and instruction B will make the configuration
> > active. If
> > we have the following instruction sequence:
> > 
> > ...
> > A1
> > B1
> > A2
> > B2
> > ...
> > 
> > A2 and B2 are the actual instructions that trigger the bug.
> > 
> > If we scan from top to bottom, after we remove A1, the behavior of
> > B1
> > might be unknowable, including not to crash the program. But we
> > will
> > successfully remove B1 later cause A2 and B2 will crash the process
> > anyway:
> > 
> > ...
> > A1
> > A2
> > B2
> > ...
> > 
> > Now one more trimming will remove A1.
> > 
> > In the perfect case, we would need to be able to remove A and B (or
> > C!) at
> > the same time. But for now, let's just add a loop around the
> > minimizer.
> > 
> > Since we only remove instructions, this iterative algorithm is
> > converging.
> > 
> > Tested with Bug 1908062.
> > 
> > Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
> 
> Small note below, but otherwise:
> Reviewed-by: Alexander Bulekov <alxndr@bu.edu>
> 
> > ---
> >  scripts/oss-fuzz/minimize_qtest_trace.py | 41 +++++++++++++++-----
> > ----
> >  1 file changed, 26 insertions(+), 15 deletions(-)
> > 
> > diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py
> > b/scripts/oss-fuzz/minimize_qtest_trace.py
> > index 1a26bf5b93..378a7ccec6 100755
> > --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> > +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> > @@ -71,21 +71,9 @@ def check_if_trace_crashes(trace, path):
> >      return False
> >  
> >  
> > -def minimize_trace(inpath, outpath):
> > -    global TIMEOUT
> > -    with open(inpath) as f:
> > -        trace = f.readlines()
> > -    start = time.time()
> > -    if not check_if_trace_crashes(trace, outpath):
> > -        sys.exit("The input qtest trace didn't cause a crash...")
> > -    end = time.time()
> > -    print("Crashed in {} seconds".format(end-start))
> > -    TIMEOUT = (end-start)*5
> > -    print("Setting the timeout for {} seconds".format(TIMEOUT))
> > -
> > -    i = 0
> > -    newtrace = trace[:]
> > +def remove_minimizer(newtrace, outpath):
> 
> Maybe a different name for this function?
> e.g. minimize_each_line or minimize_iter
> 
> -Alex

Ok, changed to remove_lines in version 5, thanks.

> 
> >      remove_step = 1
> > +    i = 0
> >      while i < len(newtrace):
> >          # 1.) Try to remove lines completely and reproduce the
> > crash.
> >          # If it works, we're done.
> > @@ -174,7 +162,30 @@ def minimize_trace(inpath, outpath):
> >                      newtrace[i] = prior[0]
> >                      del newtrace[i+1]
> >          i += 1
> > -    check_if_trace_crashes(newtrace, outpath)
> > +
> > +
> > +def minimize_trace(inpath, outpath):
> > +    global TIMEOUT
> > +    with open(inpath) as f:
> > +        trace = f.readlines()
> > +    start = time.time()
> > +    if not check_if_trace_crashes(trace, outpath):
> > +        sys.exit("The input qtest trace didn't cause a crash...")
> > +    end = time.time()
> > +    print("Crashed in {} seconds".format(end-start))
> > +    TIMEOUT = (end-start)*5
> > +    print("Setting the timeout for {} seconds".format(TIMEOUT))
> > +
> > +    newtrace = trace[:]
> > +
> > +    # remove minimizer
> > +    old_len = len(newtrace) + 1
> > +    while(old_len > len(newtrace)):
> > +        old_len = len(newtrace)
> > +        remove_minimizer(newtrace, outpath)
> > +        newtrace = list(filter(lambda s: s != "", newtrace))
> > +
> > +    assert(check_if_trace_crashes(newtrace, outpath))
> >  
> >  
> >  if __name__ == '__main__':
> > -- 
> > 2.25.1
> >