Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
From:   Denis Efremov <efremov@linux.com>
To:     Coccinelle <cocci@systeme.lip6.fr>
Cc:     Denis Efremov <efremov@linux.com>,
        Julia Lawall <julia.lawall@lip6.fr>,
        Gilles Muller <Gilles.Muller@lip6.fr>,
        Nicolas Palix <nicolas.palix@imag.fr>,
        Michal Marek <michal.lkml@markovi.net>,
        linux-kernel@vger.kernel.org
Subject: [RFC PATCH] coccinelle: check for integer overflow in binary search
Date:   Thu,  5 Sep 2019 01:12:23 +0300
Message-Id: <20190904221223.5281-1-efremov@linux.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

This is an RFC. I will resend the patch after feedback. Currently
I'm preparing big patchset with bsearch warnings fixed. The rule will
be a part of this patchset if it will be considered good enough for
checking.

There is a known integer overflow error [1] in the binary search
algorithm. Google faced it in 2006 [2]. This rule checks midpoint
calculation in binary search for overflow, i.e., (l + h) / 2.
Not every match is an actual error since the array could be small
enough. However, a custom implementation of binary search is
error-prone and it's better to use the library function (lib/bsearch.c)
or to apply defensive programming for midpoint calculation.

[1] https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues
[2] https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

Signed-off-by: Denis Efremov <efremov@linux.com>
---
 scripts/coccinelle/misc/bsearch.cocci | 80 +++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)
 create mode 100644 scripts/coccinelle/misc/bsearch.cocci

diff --git a/scripts/coccinelle/misc/bsearch.cocci b/scripts/coccinelle/misc/bsearch.cocci
new file mode 100644
index 000000000000..a99d9a8d3ee5
--- /dev/null
+++ b/scripts/coccinelle/misc/bsearch.cocci
@@ -0,0 +1,80 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/// Check midpoint calculation in binary search algorithm for integer overflow
+/// error [1]. Google faced it in 2006 [2]. Not every match is an actual error
+/// since the array can be small enough. However, a custom implementation of
+/// binary search is error-prone and it's better to use the library function
+/// (lib/bsearch.c) or to apply defensive programming for midpoint calculation.
+///
+/// [1] https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues
+/// [2] https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html
+//
+// Confidence: Medium
+// Copyright: (C) 2019 Denis Efremov, ISPRAS
+// Comments:
+// Options: --no-includes --include-headers
+
+virtual report
+virtual org
+
+@r depends on org || report@
+identifier l, h, m;
+statement S;
+position p;
+// to match 1 in <<
+// to match 2 in /
+// Can't use exact values, e.g. 2, because it fails to match 2L.
+// TODO: Is there an isomorphism for 2, 2L, 2U, 2UL, 2ULL, etc?
+constant c;
+// TODO: Is there an isomorphism for (a / 2) === (a >> 1)?
+@@
+(
+ while (\(l < h\|l <= h\|(h - l) > 1\|(l + 1) < h\|l < (h - 1)\)) {
+  ...
+(
+  ((l + h)@p / c)
+|
+  ((l + h)@p >> c)
+)
+  ...
+ }
+//TODO: Is it possible to match "do {} while ();" loops?
+// |
+//  do {
+//   ...
+// (
+//   ((l + h)@p / c)
+// |
+//   ((l + h)@p >> c)
+// )
+//   ...
+//  } while (\(l < h\|l <= h\|(h - l) > 1\|(l + 1) < h\|l < (h - 1)\));
+|
+ for (...; \(l < h\|l <= h\|(h - l) > 1\|(l + 1) < h\|l < (h - 1)\);
+      m = \(((l + h)@p / c)\|((l + h)@p >> c)\)) S
+|
+ for (...; \(l < h\|l <= h\|(h - l) > 1\|(l + 1) < h\|l < (h - 1)\); ...) {
+  ...
+(
+  ((l + h)@p / c)
+|
+  ((l + h)@p >> c)
+)
+  ...
+ }
+)
+
+@script:python depends on org@
+p << r.p;
+@@
+
+coccilib.org.print_todo(p[0], "WARNING opportunity for bsearch() or 'm = l + (h - l) / 2;'")
+
+@script:python depends on report@
+p << r.p;
+@@
+
+msg="WARNING: custom implementation of bsearch is error-prone. "
+msg+="Consider using lib/bsearch.c or fix the midpoint calculation "
+msg+="as 'm = l + (h - l) / 2;' to prevent the arithmetic overflow."
+coccilib.report.print_report(p[0], msg)
+
-- 
2.21.0