stage2

Documentation

Overview

Package stage2: mutate a sql statement.

1. visit the sub-AST defined in resources/impo.yy and get the candidate set of mutation points.

2. you can choose any mutation point to mutate, each mutation has no side effects.

How to use: If you want to choose mutation points yourself, see CalCandidates and ImpoMutate / ImpoMutateAndExec. If you want to try all of the mutation points, see MutateAll / MutateAllAndExec.

all mutations:

  FixMDistinctU
	 FixMDistinctL
	 FixMCmpOpU
	 FixMCmpOpL
	 FixMUnionAllU
	 FixMUnionAllL
  FixMInNullU
	 FixMWhere1U
	 FixMWhere0L
	 FixMHaving1U
	 FixMHaving0L
	 FixMOn1U
	 FixMOn0L
	 FixMRmUnionAllL
	 RdMLikeU
	 RdMLikeL
	 RdMRegExpU
	 RdMRegExpL

Index

• Constants
• func GenRandomStr(n int, seed int64) string
• func GenRandomValueExpr(n int, seed int64) []*test_driver.ValueExpr
• func ImpoMutate(rootNode ast.Node, candidate *Candidate, seed int64) (string, error)
• func ImpoMutateAndExec(rootNode ast.Node, candidate *Candidate, seed int64, conn connector.Connector) (string, *connector.Result, error)
• type Candidate
• type MutateResult
  • func MutateAll(sql string, seed int64) *MutateResult
  • func MutateAllAndExec(sql string, seed int64, conn *connector.Connector) *MutateResult
• type MutateUnit
• type MutateVisitor
  • func CalCandidates(sql string) (*MutateVisitor, error)

Constants

const (
	// *ast.SelectStmt: Distinct true -> false
	FixMDistinctU = "FixMDistinctU"
	// *ast.SelectStmt: Distinct false -> true
	FixMDistinctL = "FixMDistinctL"

	// *ast.SelectStmt: AfterSetOperator UNION -> UNION ALL
	FixMUnionAllU = "FixMUnionAllU"
	// *ast.SelectStmt: AfterSetOperator UNION ALL -> UNION
	FixMUnionAllL = "FixMUnionAllL"

	// *ast.BinaryOperationExpr, *ast.CompareSubqueryExpr: a {>|<|=} b -> a {>=|<=|>=} b
	FixMCmpOpU = "FixMCmpOpU"
	// *ast.BinaryOperationExpr, *ast.CompareSubqueryExpr: a {>=|<=} b -> a {>|<} b
	FixMCmpOpL = "FixMCmpOpL"

	// *ast.PatternInExpr: in(x,x,x) -> in(x,x,x,null)
	FixMInNullU = "FixMInNullU"

	// *ast.SelectStmt: WHERE xxx -> WHERE 1
	FixMWhere1U = "FixMWhere1U"
	// *ast.SelectStmt: WHERE xxx -> WHERE 0
	FixMWhere0L = "FixMWhere0L"

	// *ast.SelectStmt: HAVING xxx -> HAVING 1
	FixMHaving1U = "FixMHaving1U"
	// *ast.SelectStmt: HAVING xxx -> HAVING 0
	FixMHaving0L = "FixMHaving0L"

	// *ast.Join: ON xxx -> ON 1
	FixMOn1U = "FixMOn1U"
	// *ast.Join: ON xxx -> ON 0
	FixMOn0L = "FixMOn0L"

	// *ast.SetOprSelectList: remove Selects[1:] for UNION ALL
	FixMRmUnionAllL = "FixMRmUnionAllL"

	// *ast.PatternLikeExpr: normal char -> '_'|'%',  '_' -> '%'
	RdMLikeU = "RdMLikeU"
	// *ast.PatternLikeExpr: '%' -> '_'
	RdMLikeL = "RdMLikeL"

	// *ast.PatternRegexpExpr: '^'|'$' -> ”, normal char -> '.', '+'|'?' -> '*'
	RdMRegExpU = "RdMRegExpU"
	// *ast.PatternRegexpExpr: '*' -> '+'|'?'
	RdMRegExpL = "RdMRegExpL"
)

all mutations

Functions

func GenRandomStr

func GenRandomStr(n int, seed int64) string

GenRandomStr: generate random with length n

func GenRandomValueExpr

func GenRandomValueExpr(n int, seed int64) []*test_driver.ValueExpr

GenRandomValueExpr: generate n randome value exprs: nil, int63, float64, string(len 1~10)

func ImpoMutate

func ImpoMutate(rootNode ast.Node, candidate *Candidate, seed int64) (string, error)

ImpoMutate: you can choose any candidate calculated by CalCandidates() to mutate, each mutation has no side effects.

func ImpoMutateAndExec

func ImpoMutateAndExec(rootNode ast.Node, candidate *Candidate, seed int64,
	conn connector.Connector) (string, *connector.Result, error)

ImpoMutateAndExec: ImpoMutate + exec.

Types

type Candidate

type Candidate struct {
	MutationName string   // mutation name
	U            int      // 1: upper mutation, 0: lower mutation;
	Node         ast.Node // candidate node
	Flag         int      // 1: positive, 0: negative
}

Candidate: (mutation name, U, candidate node, Flag).

U: 1: upper mutation, 0: lower mutation;

Flag: 1: positive, 0: negative.

(U ^ Flag)^1): 1: the mutated result will expand; 0: the mutated result will shrink.

For example:

SELECT * FROM T WHERE (X > 0) IS FALSE; -- sql1
SELECT * FROM T WHERE (X >= 0) IS FALSE; -- sql2

sql(x>0) -> sql2(x>=0) is an upper mutation, U = 1. However, IS FALSE brings negative impact, Flag = 0. Therefore, the mutated result will shrink, (U ^ Flag)^1) = 0

type MutateResult

type MutateResult struct {
	MutateUnits []*MutateUnit
	Err         error
}

MutateResult: []*MutateUnit + error

func MutateAll

func MutateAll(sql string, seed int64) *MutateResult

MutateAll: For the input sql, try all of its mutation points. We will save the mutated sqls into *MutateResult.

func MutateAllAndExec

func MutateAllAndExec(sql string, seed int64, conn *connector.Connector) *MutateResult

MutateAllAndExec: MutateAll and exec.

type MutateUnit

type MutateUnit struct {
	Name    string
	Sql     string
	IsUpper bool
	Err     error

	ExecResult *connector.Result
}

MutateUnit (mutation name, mutated sql, isUpper, error, execute result).

IsUppers: true: the theoretical execution result of the current mutated statement will increase. It is actually ((Candidate.U ^ Candidate.Flag)^1) == 1

type MutateVisitor

type MutateVisitor struct {
	Root       ast.Node
	Candidates map[string][]*Candidate // mutation name : slice of *Candidate
}

MutateVisitor:

There are lots of functions under MutateVisitor, we classify them by prefix:

visitxxx: calculate Flag, call miningxxx
miningxxx: call addxxx
addxxx: add mutation U/L to Candidates

We have made a lot of effort to analyze the features of mysql:

- analyzed https://dev.mysql.com/doc/refman/8.0/en/

- analyzed all 175 ast.Node of tidb parser(https://github.com/pingcap/tidb/tree/v5.4.2/parser), of which 57 nodes are related to query, including 31 operators and 274 functions.

Through the analysis we get the following strategies:

(1) visit strategies: We recursively traverse each ast node and its descendants. Stop recursion when meet:

- numerical operations, such as |, &, ~, <<, >>, +, -, *, /(DIV), %(MOD), ^, see https://dev.mysql.com/doc/refman/8.0/en/numeric-functions.html

- logical operation XOR. we will visit the descendants of OR(||), AND(&&), NOT(!), but stop recursion when meet XOR. see https://dev.mysql.com/doc/refman/8.0/en/logical-operators.html

- comparison operations exclude IS [NOT] TRUE/IS [NOT] FALSE, such as =, >=, >, <=, <, !=, <>, <=>, IS NULL, IN, BETWEEN AND, LIKE, REGEXP. see https://dev.mysql.com/doc/refman/8.0/en/comparison-operators.html

comparison operations are important mutation points.
For convenience, we only focus on the top-level comparison operations, so we stop recursion when meet comparison operations.
Note that we will visit the descendants of IS TRUE/ IS FALSE, they are equivalent to logical operations.
Moreover, we only focus on true/false, so we do care about IS NULL, <=>, just stop recursion.

- subqueries without ANY,ALL,SOME,IN,EXISTS. such as SELECT X FROM T1 WHERE X > (SELECT 1)

- control flow. such as CASE, IF, see https://dev.mysql.com/doc/refman/8.0/en/flow-control-statements.html

- functions. Currently we do not analyze the implication in functions.

- unknown features. Although we have made a lot of effort to analyze the features of mysql, we may still be ill-considered. Therefore, we conservatively stop recursion when meet unknown features.

(2) mutation strategies: We will calculate candidate mutation points during visit, then mutate them. see allmutations.go

func CalCandidates

func CalCandidates(sql string) (*MutateVisitor, error)

CalCandidates: visit the sub-AST defined in resources/impo.yy and get the candidate set of mutation points. see MutateVisitor.

Each mutation has its own name, see:

  FixMDistinctU
	 FixMDistinctL
	 FixMCmpOpU
	 FixMCmpOpL
	 FixMUnionAllU
	 FixMUnionAllL
  FixMInNullU
	 FixMWhere1U
	 FixMWhere0L
	 FixMHaving1U
	 FixMHaving0L
	 FixMOn1U
	 FixMOn0L
	 FixMRmUnionAllL
	 RdMLikeU
	 RdMLikeL
	 RdMRegExpU
	 RdMRegExpL

about the prefix {FixM|RdM}(currently not working):

FixM means fixed mutation;
RdM means random mutation;

about the suffix {U|L}:

U means upper mutation,
L means lower mutation.