CVE-2022-23628: Incorrect Calculation (CWE-682)
value: OPA is an open source, general-purpose policy engine. Under certain conditions, pretty-printing an abstract syntax tree (AST) that contains synthetic nodes could change the logic of some statements by reordering array literals. Example of policies impacted are those that parse and compare web paths. **All of these** three conditions have to be met to create an adverse effect: 1. An AST of Rego had to be **created programmatically** such that it ends up containing terms without a location (such as wildcard variables). 2. The AST had to be **pretty-printed** using the `github.com/open-policy-agent/opa/format` package. 3. The result of the pretty-printing had to be **parsed and evaluated again** via an OPA instance using the bundles, or the Golang packages. If any of these three conditions are not met, you are not affected. Notably, all three would be true if using **optimized bundles**, i.e. bundles created with `opa build -O=1` or higher. In that case, the optimizer would fulfil condition (1.), the result of that would be pretty-printed when writing the bundle to disk, fulfilling (2.). When the bundle was then used, we'd satisfy (3.). As a workaround users may disable optimization when creating bundles.
CWE description: The product performs a calculation that generates incorrect or unintended results that are later used in security-critical decisions or resource management.
CVSS v3 base score: 5.3
Published: 2022-02-09T22:15Z
Repository: https://github.com/open-policy-agent/opa
Language: Go
Files changed: format/format.go, format/format_test.go
Commit date: 2022-01-25 08:43:20 +0100
Commit message: format: don't group iterable when one has defaulted location (#4260)

As mentioned in the comment, empty file names happen when the format
package's Ast() function does a sweep of its input, and adds a
"default location" to everything that has a nil location.

During PE, when generated the pairs to save in saveUnify, we'll
return Var Terms without locations. Fixing that seemed like a bigger
hurdle, so I went this route.

The new check is such that if any term has the default file in
its location, such as would happen if we're formatting code that
was created programmatically (not parsed), we'll group the terms'
elements, but print them in one line.

Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
Diff: diff --git a/format/format.go b/format/format.go
index 3e6c9b41..16e6bf33 100644
--- a/format/format.go
+++ b/format/format.go
@@ -12,10 +12,15 @@ import (
 	"sort"
 
 	"github.com/open-policy-agent/opa/ast"
 )
 
+// defaultLocationFile is the file name used in `Ast()` for terms
+// without a location, as could happen when pretty-printing the
+// results of partial eval.
+const defaultLocationFile = "__format_default__"
+
 // Source formats a Rego source file. The bytes provided must describe a complete
 // Rego module. If they don't, Source will return an error resulting from the attempt
 // to parse the bytes.
 func Source(filename string, src []byte) ([]byte, error) {
 	module, err := ast.ParseModule(filename, string(src))
@@ -152,11 +157,11 @@ func squashTrailingNewlines(bs []byte) []byte {
 	}
 	return bs
 }
 
 func defaultLocation(x ast.Node) *ast.Location {
-	return ast.NewLocation([]byte(x.String()), "", 1, 1)
+	return ast.NewLocation([]byte(x.String()), defaultLocationFile, 1, 1)
 }
 
 type writer struct {
 	buf bytes.Buffer
 
@@ -893,26 +898,31 @@ func (w *writer) listWriter() entryWriter {
 
 // groupIterable will group the `elements` slice into slices according to their
 // location: anything on the same line will be put into a slice.
 func groupIterable(elements []interface{}, last *ast.Location) [][]interface{} {
 	// Generated vars occur in the AST when we're rendering the result of
-	// partial evaluation in a bundle build with optimization. For those vars,
-	// there is no location, and the grouping based on source location will
-	// yield a bad result. So if there's a generated variable among elements,
-	// we'll render the elements all in one line.
-	vis := ast.NewVarVisitor()
+	// partial evaluation in a bundle build with optimization.
+	// Those variables, and wildcard variables have the "default location",
+	// set in `Ast()`). That is no proper file location, and the grouping
+	// based on source location will yield a bad result.
+	def := false // default location found?
 	for _, elem := range elements {
-		vis.Walk(elem)
-	}
-	for v := range vis.Vars() {
-		if v.IsGenerated() {
+		ast.WalkTerms(elem, func(t *ast.Term) bool {
+			if t.Location.File == defaultLocationFile {
+				def = true
+				return true
+			}
+			return false
+		})
+		if def { // return as-is
 			return [][]interface{}{elements}
 		}
 	}
 	sort.Slice(elements, func(i, j int) bool {
 		return locLess(elements[i], elements[j])
 	})
+
 	var lines [][]interface{}
 	var cur []interface{}
 	for i, t := range elements {
 		elem := t
 		loc := getLoc(elem)
diff --git a/format/format_test.go b/format/format_test.go
index 52d36b67..51194576 100644
--- a/format/format_test.go
+++ b/format/format_test.go
@@ -334,10 +334,56 @@ a[_x[y]]`,
 				},
 			},
 			expected: `_x
 a[_x[y][[z, w]]]`,
 		},
+		{
+			note: "expr with wildcard that has a default location",
+			toFmt: func() *ast.Expr {
+				expr := ast.MustParseExpr(`["foo", _] = split(input.foo, ":")`)
+				ast.WalkTerms(expr, func(term *ast.Term) bool {
+					v, ok := term.Value.(ast.Var)
+					if ok && v.IsWildcard() {
+						term.Location = defaultLocation(term)
+						return true
+					}
+					term.Location.File = "foo.rego"
+					term.Location.Row = 2
+					return false
+				})
+				return expr
+			}(),
+			expected: `["foo", _] = split(input.foo, ":")`,
+		},
+		{
+			note: "expr all terms having empty-file locations",
+			toFmt: ast.MustParseExpr(`[
+					"foo",
+					_
+					] = split(input.foo, ":")`),
+			expected: `
+[
+	"foo",
+	_,
+] = split(input.foo, ":")`,
+		},
+		{
+			note: "expr where all terms having empty-file locations, and one is a default location",
+			toFmt: func() *ast.Expr {
+				expr := ast.MustParseExpr(`
+["foo", __local1__] = split(input.foo, ":")`)
+				ast.WalkTerms(expr, func(term *ast.Term) bool {
+					if ast.VarTerm("__local1__").Equal(term) {
+						term.Location = defaultLocation(term)
+						return true
+					}
+					return false
+				})
+				return expr
+			}(),
+			expected: `["foo", __local1__] = split(input.foo, ":")`,
+		},
 	}
 
 	for _, tc := range cases {
 		t.Run(tc.note, func(t *testing.T) {
 			bs, err := Ast(tc.toFmt)
@@ -345,11 +391,11 @@ a[_x[y][[z, w]]]`,
 				t.Fatalf("Unexpected error: %s", err)
 			}
 			expected := strings.TrimSpace(tc.expected)
 			actual := strings.TrimSpace(string(bs))
 			if actual != expected {
-				t.Fatalf("Expected:\n\n%s\n\nGot:\n\n%s\n\n", expected, actual)
+				t.Fatalf("Expected:\n\n%q\n\nGot:\n\n%q\n\n", expected, actual)
 			}
 		})
 	}
 }
 

Vulnerable code: 	return ast.NewLocation([]byte(x.String()), "", 1, 1)
	// partial evaluation in a bundle build with optimization. For those vars,
	// there is no location, and the grouping based on source location will
	// yield a bad result. So if there's a generated variable among elements,
	// we'll render the elements all in one line.
	vis := ast.NewVarVisitor()
		vis.Walk(elem)
	}
	for v := range vis.Vars() {
		if v.IsGenerated() {
				t.Fatalf("Expected:\n\n%s\n\nGot:\n\n%s\n\n", expected, actual)
Fixed code: // defaultLocationFile is the file name used in `Ast()` for terms
// without a location, as could happen when pretty-printing the
// results of partial eval.
const defaultLocationFile = "__format_default__"

	return ast.NewLocation([]byte(x.String()), defaultLocationFile, 1, 1)
	// partial evaluation in a bundle build with optimization.
	// Those variables, and wildcard variables have the "default location",
	// set in `Ast()`). That is no proper file location, and the grouping
	// based on source location will yield a bad result.
	def := false // default location found?
		ast.WalkTerms(elem, func(t *ast.Term) bool {
			if t.Location.File == defaultLocationFile {
				def = true
				return true
			}
			return false
		})
		if def { // return as-is

		{
			note: "expr with wildcard that has a default location",
			toFmt: func() *ast.Expr {
				expr := ast.MustParseExpr(`["foo", _] = split(input.foo, ":")`)
				ast.WalkTerms(expr, func(term *ast.Term) bool {
					v, ok := term.Value.(ast.Var)
					if ok && v.IsWildcard() {
						term.Location = defaultLocation(term)
						return true
					}
					term.Location.File = "foo.rego"
					term.Location.Row = 2
					return false
				})
				return expr
			}(),
			expected: `["foo", _] = split(input.foo, ":")`,
		},
		{
			note: "expr all terms having empty-file locations",
			toFmt: ast.MustParseExpr(`[
					"foo",
					_
					] = split(input.foo, ":")`),
			expected: `
[
	"foo",
	_,
] = split(input.foo, ":")`,
		},
		{
			note: "expr where all terms having empty-file locations, and one is a default location",
			toFmt: func() *ast.Expr {
				expr := ast.MustParseExpr(`
["foo", __local1__] = split(input.foo, ":")`)
				ast.WalkTerms(expr, func(term *ast.Term) bool {
					if ast.VarTerm("__local1__").Equal(term) {
						term.Location = defaultLocation(term)
						return true
					}
					return false
				})
				return expr
			}(),
			expected: `["foo", __local1__] = split(input.foo, ":")`,
		},
				t.Fatalf("Expected:\n\n%q\n\nGot:\n\n%q\n\n", expected, actual)