Skip to contentSkip to conversation

coccinelle: check for integer overflow in binary search

RFC PATCH In review Denis Efremov 3 participants 6 messages Sep 4, 2019 – Sep 5, 2019

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 coccinelle: check for integer overflow in binary search

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

---
 scripts/coccinelle/misc/bsearch.cocci | 80 +++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)
 create mode 100644 scripts/coccinelle/misc/bsearch.cocci
scripts/coccinelle/misc/bsearch.cocci new file +80 -0
new file mode 100644
index 000000000000..a99d9a8d3ee5
@@ -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)
+
Signature · 1 line
2.21.0
#1 lore raw
Quoted 45 lines · Denis Efremov

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

---
 scripts/coccinelle/misc/bsearch.cocci | 80 +++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)
 create mode 100644 scripts/coccinelle/misc/bsearch.cocci
scripts/coccinelle/misc/bsearch.cocci new file +17 -0
new file mode 100644
index 000000000000..a99d9a8d3ee5
@@ -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

scripts/coccinelle/misc/bsearch.cocci line 27

Quoted 10 lines
scripts/coccinelle/misc/bsearch.cocci new file +10 -0
+
+@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;

As far as I can see, you aren't checking for 2 at all at the moment? You should be able to say constant c = {2, 2L, etc};. Actually, we do consider several variants of 0, so it could be reasonable to allow eg 2 to match other variants as well.

scripts/coccinelle/misc/bsearch.cocci line 28

Quoted 1 line
scripts/coccinelle/misc/bsearch.cocci new file +1 -0
+// TODO: Is there an isomorphism for (a / 2) === (a >> 1)?

No. I'm not sure it's common enough to be worth it. But it could be added if it seems like a good idea.

scripts/coccinelle/misc/bsearch.cocci line 40

Quoted 12 lines
scripts/coccinelle/misc/bsearch.cocci new file +12 -0
+@@
+(
+ 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?

Not at the moment. There is some work on it, but it is not complete (adding Evan in CC).

julia

Quoted 44 lines
scripts/coccinelle/misc/bsearch.cocci new file +40 -1
+// |
+//  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

#2 lore raw
Quoted 53 lines · Julia Lawall
Quoted 49 lines · Denis Efremov

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

---
 scripts/coccinelle/misc/bsearch.cocci | 80 +++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)
 create mode 100644 scripts/coccinelle/misc/bsearch.cocci
scripts/coccinelle/misc/bsearch.cocci new file +21 -0
new file mode 100644
index 000000000000..a99d9a8d3ee5
@@ -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;
Quoted 8 lines

scripts/coccinelle/misc/bsearch.cocci line 27

Quoted 6 lines
scripts/coccinelle/misc/bsearch.cocci new file +6 -0
+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;

As far as I can see, you aren't checking for 2 at all at the moment?

Yes, there are no false positives even without pinning constants to 1, 2. However, it's better to express this in the rule.

Quoted 4 lines

You
should be able to say constant c = {2, 2L, etc};. Actually, we do consider several variants of 0, so it could be reasonable to allow eg 2 to match other variants as well.

It looks like integer literals aren't fully supported. When I'm trying to write 'constant c = {2L}; ' it fails with int_of_string error.

Denis

#3 lore raw
Quoted 68 lines · Denis Efremov
Quoted 53 lines · Julia Lawall
Quoted 49 lines · Denis Efremov

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

---
 scripts/coccinelle/misc/bsearch.cocci | 80 +++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)
 create mode 100644 scripts/coccinelle/misc/bsearch.cocci
scripts/coccinelle/misc/bsearch.cocci new file +21 -0
new file mode 100644
index 000000000000..a99d9a8d3ee5
@@ -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;
Quoted 8 lines

scripts/coccinelle/misc/bsearch.cocci line 27

Quoted 6 lines
scripts/coccinelle/misc/bsearch.cocci new file +6 -0
+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;

As far as I can see, you aren't checking for 2 at all at the moment?

Yes, there are no false positives even without pinning constants to 1, 2. However, it's better to express this in the rule.

Quoted 7 lines
Quoted 4 lines

You
should be able to say constant c = {2, 2L, etc};. Actually, we do consider several variants of 0, so it could be reasonable to allow eg 2 to match other variants as well.

It looks like integer literals aren't fully supported. When I'm trying to write 'constant c = {2L}; ' it fails with int_of_string error.

Oops. I'll fix it, but since people may be using older versions of Coccinelle, perhaps it is not worth taking this strategy in this case. Could you make a disjunction, or check for the proper value in the python code?

julia

#4 lore raw
In reply to Denis Efremov
Quoted 1 line

+identifier l, h, m;

Can expressions make sense for these metavariables?

scripts/coccinelle/misc/bsearch.cocci line 39

Quoted 11 lines

+@@

scripts/coccinelle/misc/bsearch.cocci new file +10 -0
+(
+ while (\(l < h\|l <= h\|(h - l) > 1\|(l + 1) < h\|l < (h - 1)\)) {
+  ...
+(
+  ((l + h)@p / c)
+|
+  ((l + h)@p >> c)
+)
+  ...
+ }

* I suggest again to look at further possibilities to reduce undesirable code duplication also together with the usage of SmPL disjunctions.

* The condition specification might be easier to read with a few additional spaces (or the following variant).

* The SmPL ellipses will probably need further considerations.

+@@
+(
+ while (

+(       l \( < \| <= \) h
+|       (h - l) > 1
+|       (h - 1) > l
+|       (l + 1) < h

+) )
+ {
+ <+...
+ ((l + h)@p \( / \| >> \) c)
+ ...+>
+ }

scripts/coccinelle/misc/bsearch.cocci line 79

Quoted 8 lines

+@script:python depends on report@

scripts/coccinelle/misc/bsearch.cocci new file +7 -0
+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)

The Linux coding style supports to put a long string literal also into a single line. Thus I find such a message construction nicer without the extra variable “msg”.

Regards,
Markus

#5 lore raw
In reply to Denis Efremov
Quoted 3 lines

+@@
+(
+ while (\(…\)) {

…

Quoted 1 line

+ }

It seems that compound statements are mainly checked for control flow statements by this source code search approach so far.
Would you like to handle also single statements (without the curly brackets)?
(Will additional SmPL disjunctions be needed then?)

Quoted 1 line

+statement S;

…

Quoted 3 lines

+|
+ for (...; \(…\);
+ m = \(…\)) S

* Can the metavariable “S” look nicer on a separate line?

* Should assignments be taken into account for more variables?

Quoted 4 lines

+|
+ for (...; \(…\); ...) {
+ }
+)

I find the shown case distinction incomplete.
Will loop initialisations trigger further SmPL development challenges?

Regards,
Markus