feat: static checking for common bug patterns #10190

tomtau · 2021-09-17T06:47:33Z

Summary

It'd be good to add GH Action that would statically check for common bug patterns -- e.g. https://github.com/github/codeql-action

Problem Definition

There are a few bugs that resurfaced a few times in Cosmos SDK -- off the top of my head, I can think of:

non-determinism through iterating over Go maps
using hardcoded constants instead of values from application configs (e.g. fix bech32 prefix in evidence #8461 fix validator address prefix #9212 )

It would be good to capture these sorts of bug patterns in static analysis tools, so that it's less likely to re-introduce them.

Add CodeQL Github Action pipeline: https://github.com/github/codeql-action
and write a few custom CodeQL queries to capture common bugs from the past: https://codeql.github.com/docs/codeql-language-guides/codeql-for-go/

For Admin Use

Not duplicate issue
Appropriate labels applied
Appropriate contributors tagged
Contributor assigned/self-assigned

tomtau · 2021-10-15T03:43:41Z

one simple query to detect iterations over maps:

/**
 * @name Iteration over map 
 * @kind problem
 * @description Iteration over map is non-deterministic and could cause issues in consensus-critical code.
 * @problem.severity warning
 * @tags correctness
 * @precision low
 * @security-severity medium
 * @id go/example/map-iteration
 */

import go

from RangeStmt loop
where loop.getDomain().getType() instanceof MapType
select loop, "Iteration over map"

In Cosmos SDK, there are 59 cases: https://lgtm.com/query/5686749966483880627/ -- FYI @ryanchristo @robert-zaremba -- it may be good to go over them to check they are harmless.

I guess that query could be added to CI as it is, but alternatively, we can also refine it for a higher precision: https://codeql.github.com/docs/codeql-language-guides/modeling-data-flow-in-go-libraries/

The more precise query would be something like: find all iterations over map which are one of these options:

they get to be executed on ABCI consensus-related methods (beginblock, DeliverTx, ...)
they write to a field or a variable that gets read on ABCI consensus-related methods and they were not sorted
...

tac0turtle · 2021-10-15T10:01:42Z

cc @odeke-em

tomtau · 2021-10-27T02:27:00Z

besides map iteration, I guess it'd be good to have queries to scan for other sources of non-determinism -- as with https://forum.cosmos.network/t/cosmos-sdk-vulnerability-retrospective-security-advisory-jackfruit-october-12-2021/5349 -- time.Now()

tomtau · 2021-11-01T07:58:38Z

I tried to exclude test and telemetry usage of time.Now():

/**
 * @name Calling the system time
 * @description Calling the system time is non-deterministic and could cause issues in consensus-critical code.
 * @kind problem
 * @problem.severity warning
 * @id go/system-time
 * @tags correctness
 */

import go

predicate isIrrelevantPackage(string packageName) {
  packageName = "cli" or packageName = "main" or packageName = "testutil"
}

from CallExpr call
where
  call.getTarget().getQualifiedName() = "time.Now" and
  // TODO: uncomment if ignoring string formatting is desired
  // not (
  //   call.getParent().(CallExpr).getTarget().getQualifiedName() =
  //     "github.com/cosmos/cosmos-sdk/types.FormatTimeBytes" or
  //   call.getParent*().(CallExpr).getTarget().getQualifiedName().matches("fmt.Sprintf")
  // ) and
  not call.getEnclosingFunction().getName().matches("Test%") and
  call.getLocation().getFile().getBaseName() != "test_helpers.go" and
  not isIrrelevantPackage(call.getLocation().getFile().getPackageName()) and
  not exists(DataFlow::CallNode telemetryCall |
    telemetryCall
        .getExpr()
        .(CallExpr)
        .getTarget()
        .getQualifiedName()
        .matches("github.com/cosmos/cosmos-sdk/telemetry%")
  |
    DataFlow::localFlow(DataFlow::exprNode(call), telemetryCall.getAnArgument())
  )
select call, "Calling the system time"

There are 5 results in the current master: https://lgtm.com/query/1044813113192157603/ including that problem in authz

tomtau · 2021-11-01T09:49:44Z

There are no results in the current master:

/**
 * @name Directly using the bech32 constants
 * @description Bech32 constants are hardcoded to Gaia defaults; the external applications would need to use `GetConfig().GetBech32...` functions instead of constants
 * @kind problem
 * @problem.severity warning
 * @id go/bech-32-constant
 * @tags correctness
 */

import go

from ConstantName cn
where
  cn.toString().matches("Bech32%") and
  cn.getLocation().getFile().getPackageName() != "types"
select cn, "Directly using the bech32 constants"

but I verified that running this query locally on a DB built from SDK v0.41.4, it'll have 33 findings.

tomtau · 2021-11-02T02:42:07Z

In some SDK projects, floating point operations were parts of bugs, so it may be good to flag them too:

/**
 * @name Floating point arithmetic
 * @kind problem
 * @description Floating point operations are not associative and may lead to surprising situations: https://en.wikipedia.org/wiki/Floating-point_arithmetic#Accuracy_problems
 * @problem.severity recommendation
 * @tags correctness
 * @precision low
 * @security-severity low
 * @id go/floating-point-arithmetic
 */

import go

from ArithmeticBinaryExpr e
where
  (
    e.getLeftOperand().getType() instanceof FloatType or
    e.getRightOperand().getType() instanceof FloatType
  ) and
  e.getLocation().getFile().getPackageName() != "simulation"
select e, "Floating point arithmetic"

tomtau · 2021-11-02T10:08:00Z

I tried to collect all the queries in this repo: https://github.com/crypto-com/cosmos-sdk-codeql

robert-zaremba · 2021-11-02T23:38:03Z

Thanks for the issue. Anything in client, cli and tests can be ignored. This is definitely needed and please feel free to create a PR. It seams that all / most of them are false positives. As Bez noted in the chat, we will need some statement to ignore that false positives.

PS: this is related to : #10329

Closes cosmos#10190 added a basic GH Action pipeline for CodeQL that checks general security and code quality issues plus a few custom queries for Cosmos SDK defined in https://github.com/crypto-com/cosmos-sdk-codeql

… value This pass exists to curtail non-determinism in the cosmos-sdk which stemmed from iterating over maps during upgrades and that caused a chaotic debug for weeks. With this change, we'll now enforce and report failed iterations, with the rule being that a map in a range should involve ONLY one of these 2 operations: * for k := range m { delete(m, k) } for fast map clearing * for k := range m { keys = append(keys, k) } to retrieve keys & sort thus we shall get this report: ```shell [gosec] 2021/11/09 03:18:57 Rule error: *sdk.mapRanging => the value in the range statement should be nil: want: for key := range m (main.go:19) [gosec] 2021/11/09 03:18:57 Rule error: *sdk.mapRanging => the value in the range statement should be nil: want: for key := range m (main.go:27) ``` from the code below: ```go package main func main() { m := map[string]int{ "a": 0, "b": 1, "c": 2, "d": 3, } makeMap := func() map[string]string { return nil } keys := make([]string, 0, len(m)) for k := range m { keys = append(keys, k) } values := make([]int, 0, len(m)) for _, value := range m { values = append(values, value) } type kv struct { k, v interface{} } kvL := make([]*kv, 0, len(m)) for k, v := range m { kvL = append(kvL, &kv{k, v}) } for k := range m { delete(m, k) } for k := range makeMap() { delete(m, k) } for k := range do() { delete(m, k) } } func do() map[string]string { return nil } ``` Updates cosmos/cosmos-sdk#10190

odeke-em · 2021-11-09T03:34:54Z

We've got unreleased code in a private repo (collabo between Informal Systems * Orijtech Inc) that has a static analyzer/pass that'll detect when maps are being iterated over with values and enforce keys must be iterated upon then perhaps sorted. Kindly cc-ing @ebuchman

… value This pass exists to curtail non-determinism in the cosmos-sdk which stemmed from iterating over maps during upgrades and that caused a chaotic debug for weeks. With this change, we'll now enforce and report failed iterations, with the rule being that a map in a range should involve ONLY one of these 2 operations: * for k := range m { delete(m, k) } for fast map clearing * for k := range m { keys = append(keys, k) } to retrieve keys & sort thus we shall get this report: ```shell [gosec] 2021/11/09 03:18:57 Rule error: *sdk.mapRanging => the value in the range statement should be nil: want: for key := range m (main.go:19) [gosec] 2021/11/09 03:18:57 Rule error: *sdk.mapRanging => the value in the range statement should be nil: want: for key := range m (main.go:27) ``` from the code below: ```go package main func main() { m := map[string]int{ "a": 0, "b": 1, "c": 2, "d": 3, } makeMap := func() map[string]string { return nil } keys := make([]string, 0, len(m)) for k := range m { keys = append(keys, k) } values := make([]int, 0, len(m)) for _, value := range m { values = append(values, value) } type kv struct { k, v interface{} } kvL := make([]*kv, 0, len(m)) for k, v := range m { kvL = append(kvL, &kv{k, v}) } for k := range m { delete(m, k) } for k := range makeMap() { delete(m, k) } for k := range do() { delete(m, k) } } func do() map[string]string { return nil } ``` Updates cosmos/cosmos-sdk#10190

## Description Closes: #10190 added a basic GH Action pipeline for CodeQL that checks general security and code quality issues plus a few custom queries for Cosmos SDK defined in https://github.com/crypto-com/cosmos-sdk-codeql --- ### Author Checklist *All items are required. Please add a note to the item if the item is not applicable and please add links to any relevant follow up issues.* I have... - [x] included the correct [type prefix](https://github.com/commitizen/conventional-commit-types/blob/v3.0.0/index.json) in the PR title - [ ] added `!` to the type prefix if API or client breaking change - [x] targeted the correct branch (see [PR Targeting](https://github.com/cosmos/cosmos-sdk/blob/master/CONTRIBUTING.md#pr-targeting)) - [x] provided a link to the relevant issue or specification - [ ] followed the guidelines for [building modules](https://github.com/cosmos/cosmos-sdk/blob/master/docs/building-modules) - [ ] included the necessary unit and integration [tests](https://github.com/cosmos/cosmos-sdk/blob/master/CONTRIBUTING.md#testing) - [ ] added a changelog entry to `CHANGELOG.md` - [ ] included comments for [documenting Go code](https://blog.golang.org/godoc) - [ ] updated the relevant documentation or specification - [x] reviewed "Files changed" and left comments if necessary - [x] confirmed all CI checks have passed ### Reviewers Checklist *All items are required. Please add a note if the item is not applicable and please add your handle next to the items reviewed if you only reviewed selected items.* I have... - [ ] confirmed the correct [type prefix](https://github.com/commitizen/conventional-commit-types/blob/v3.0.0/index.json) in the PR title - [ ] confirmed `!` in the type prefix if API or client breaking change - [ ] confirmed all author checklist items have been addressed - [ ] reviewed state machine logic - [ ] reviewed API design and naming - [ ] reviewed documentation is accurate - [ ] reviewed tests and test coverage - [ ] manually tested (if applicable)

… value This pass exists to curtail non-determinism in the cosmos-sdk which stemmed from iterating over maps during upgrades and that caused a chaotic debug for weeks. With this change, we'll now enforce and report failed iterations, with the rule being that a map in a range should involve ONLY one of these 2 operations: * for k := range m { delete(m, k) } for fast map clearing * for k := range m { keys = append(keys, k) } to retrieve keys & sort thus we shall get this report: ```shell [gosec] 2021/11/09 03:18:57 Rule error: *sdk.mapRanging => the value in the range statement should be nil: want: for key := range m (main.go:19) [gosec] 2021/11/09 03:18:57 Rule error: *sdk.mapRanging => the value in the range statement should be nil: want: for key := range m (main.go:27) ``` from the code below: ```go package main func main() { m := map[string]int{ "a": 0, "b": 1, "c": 2, "d": 3, } makeMap := func() map[string]string { return nil } keys := make([]string, 0, len(m)) for k := range m { keys = append(keys, k) } values := make([]int, 0, len(m)) for _, value := range m { values = append(values, value) } type kv struct { k, v interface{} } kvL := make([]*kv, 0, len(m)) for k, v := range m { kvL = append(kvL, &kv{k, v}) } for k := range m { delete(m, k) } for k := range makeMap() { delete(m, k) } for k := range do() { delete(m, k) } } func do() map[string]string { return nil } ``` Updates cosmos/cosmos-sdk#10189 Updates cosmos/cosmos-sdk#10188 Updates cosmos/cosmos-sdk#10190

## Description Closes: cosmos#10190 added a basic GH Action pipeline for CodeQL that checks general security and code quality issues plus a few custom queries for Cosmos SDK defined in https://github.com/crypto-com/cosmos-sdk-codeql --- ### Author Checklist *All items are required. Please add a note to the item if the item is not applicable and please add links to any relevant follow up issues.* I have... - [x] included the correct [type prefix](https://github.com/commitizen/conventional-commit-types/blob/v3.0.0/index.json) in the PR title - [ ] added `!` to the type prefix if API or client breaking change - [x] targeted the correct branch (see [PR Targeting](https://github.com/cosmos/cosmos-sdk/blob/master/CONTRIBUTING.md#pr-targeting)) - [x] provided a link to the relevant issue or specification - [ ] followed the guidelines for [building modules](https://github.com/cosmos/cosmos-sdk/blob/master/docs/building-modules) - [ ] included the necessary unit and integration [tests](https://github.com/cosmos/cosmos-sdk/blob/master/CONTRIBUTING.md#testing) - [ ] added a changelog entry to `CHANGELOG.md` - [ ] included comments for [documenting Go code](https://blog.golang.org/godoc) - [ ] updated the relevant documentation or specification - [x] reviewed "Files changed" and left comments if necessary - [x] confirmed all CI checks have passed ### Reviewers Checklist *All items are required. Please add a note if the item is not applicable and please add your handle next to the items reviewed if you only reviewed selected items.* I have... - [ ] confirmed the correct [type prefix](https://github.com/commitizen/conventional-commit-types/blob/v3.0.0/index.json) in the PR title - [ ] confirmed `!` in the type prefix if API or client breaking change - [ ] confirmed all author checklist items have been addressed - [ ] reviewed state machine logic - [ ] reviewed API design and naming - [ ] reviewed documentation is accurate - [ ] reviewed tests and test coverage - [ ] manually tested (if applicable)

ryanchristo assigned odeke-em Sep 17, 2021

This was referenced Nov 2, 2021

Add static checking for common bug patterns confio/tgrade#173

Closed

Add static checking for common bug patterns CosmWasm/wasmd#667

Closed

tomtau mentioned this issue Nov 3, 2021

feat: static checking for common bug patterns #10488

Merged

19 tasks

odeke-em mentioned this issue Nov 9, 2021

rules/sdk: implement pass to only permit key iteration over maps, not value cosmos/gosec#5

Merged

mergify bot closed this as completed in #10488 Nov 9, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: static checking for common bug patterns #10190

feat: static checking for common bug patterns #10190

tomtau commented Sep 17, 2021 •

edited by robert-zaremba

Loading

tomtau commented Oct 15, 2021

tac0turtle commented Oct 15, 2021

tomtau commented Oct 27, 2021

tomtau commented Nov 1, 2021

tomtau commented Nov 1, 2021

tomtau commented Nov 2, 2021

tomtau commented Nov 2, 2021

robert-zaremba commented Nov 2, 2021

odeke-em commented Nov 9, 2021

feat: static checking for common bug patterns #10190

feat: static checking for common bug patterns #10190

Comments

tomtau commented Sep 17, 2021 • edited by robert-zaremba Loading

Summary

Problem Definition

Proposal

For Admin Use

tomtau commented Oct 15, 2021

tac0turtle commented Oct 15, 2021

tomtau commented Oct 27, 2021

tomtau commented Nov 1, 2021

tomtau commented Nov 1, 2021

tomtau commented Nov 2, 2021

tomtau commented Nov 2, 2021

robert-zaremba commented Nov 2, 2021

odeke-em commented Nov 9, 2021

tomtau commented Sep 17, 2021 •

edited by robert-zaremba

Loading