Go AST 淺析與 CTF 中的實戰運用
前言
在前段時間的網鼎杯某賽道中遇到了一個題，通過混淆的 go 源碼分析各類函數調用、定義信息。但由於題目本身要求獲得的信息過於簡單，有不少人直接暴力搜索來解決。但當我們遇到更爲複雜，更爲巨大的混淆代碼時，IDE 所提供的簡單分析功能也就無能爲力了。這也就是我寫下這篇文章的原因。
What are ASTs?
AST，即抽象語法樹 (Abstract Syntax Tree)，也被簡稱爲語法樹，是源代碼的抽象語法結構的樹狀顯示。其中樹上的每個節點代表着源代碼中的一種結構。AST 並不是一種編程語言特有的。JavaScript、C/C++、Python、Go 等幾乎所有的編程語言都有 AST。只是其編譯器各不相同。
正如孩提時代總喜歡玩的積木那般，我們將其組裝，而後將其拆解，再次又將其組裝成 “新” 玩具。是的。通過 AST，我們可以將我們的源代碼拆解開來，而後根據我們的意願進行組裝。
你是否想過，我們常用的 IDE 所具備的各類功能：語法高亮、自動補全、錯誤提示、代碼格式化、代碼壓縮等等其實都是通過 AST 來實現的。
Token
Token 是編程語言中最小的具有獨立意義的詞法單元。Token 不僅包含關鍵字，還包含了各種用戶自定義的標識符、運算符、分隔符和註釋等。
Token 對應的詞法單元有三個重要屬性：
- Token 本身的值表示詞法單元的類型
- Token 在源代碼中的表現形式
- Token 出現的位置
在 Token 中，較爲特殊的是註釋和分號。普通的註釋並不影響程序的語義，因此在某些情況下，我們可以忽略註釋。
正如上文所說的，Go 語言也由標識符、運算符等 Token 組成。其中標識符的語法定義如下。
identifier = letter { letter | unicode_digit } .
letter = unicode_letter | "_" .其中 identifier 表示標識符，由字母和數字組成，開頭必須爲字母，較爲特殊的，下劃線也被視作字母。因此我們可以使用下劃線作爲標識符。
Token 的定義在go/token中。
// Token is the set of lexical tokens of the Go programming language.
type Token intToken 被定義爲一種枚舉值，不同值的 Token 表示不同類型的詞法記號。
// The list of tokens.
const (
// Special tokens
ILLEGAL Token = iota
EOF
COMMENT
literal_beg
// Identifiers and basic type literals
// (these tokens stand for classes of literals)
IDENT // main
INT // 12345
FLOAT // 123.45
IMAG // 123.45i
CHAR // 'a'
STRING // "abc"
literal_end
operator_beg
// Operators and delimiters
ADD // +
SUB // -
MUL // *
QUO // /
REM // %
AND // &
OR // |
XOR // ^
SHL // <<
SHR // >>
AND_NOT // &^
ADD_ASSIGN // +=
SUB_ASSIGN // -=
MUL_ASSIGN // *=
QUO_ASSIGN // /=
REM_ASSIGN // %=
AND_ASSIGN // &=
OR_ASSIGN // |=
XOR_ASSIGN // ^=
SHL_ASSIGN // <<=
SHR_ASSIGN // >>=
AND_NOT_ASSIGN // &^=
LAND // &&
LOR // ||
ARROW // <-
INC // ++
DEC // --
EQL // ==
LSS // <
GTR // >
ASSIGN // =
NOT // !
NEQ // !=
LEQ // <=
GEQ // >=
DEFINE // :=
ELLIPSIS // ...
LPAREN // (
LBRACK // [
LBRACE // {
COMMA // ,
PERIOD // .
RPAREN // )
RBRACK // ]
RBRACE // }
SEMICOLON // ;
COLON // :
operator_end
keyword_beg
// Keywords
BREAK
CASE
CHAN
CONST
CONTINUE
DEFAULT
DEFER
ELSE
FALLTHROUGH
FOR
FUNC
GO
GOTO
IF
IMPORT
INTERFACE
MAP
PACKAGE
RANGE
RETURN
SELECT
STRUCT
SWITCH
TYPE
VAR
keyword_end
additional_beg
// additional tokens, handled in an ad-hoc manner
TILDE
additional_end
)所有的 Token 被分爲四類：特殊類型的 Token、基礎面值對應的 Token、運算符 Token 和關鍵字。
需要注意的是這裏的*_beg是私有類型，主要用於值域範圍範圍的判斷。
FileSet & File
Go 語言是由多個文件組成的包，而後多個包鏈接爲一個可執行文件，因此單個包對應的多個文件可被視作 Go 的基本編譯單元。
因此就有了go/token中的 FileSet 和 File 對象。用於描述文件以及對應的文件集合。
FileSet 的結構如下所示。
type FileSet struct {
mutex sync.RWMutex // protects the file set
base int // base offset for the next file
files []*File // list of files in the order added to the set
last atomic.Pointer[File] // cache of last file looked up
}File 的結構如下所示。
type File struct {
name string // file name as provided to AddFile
base int // Pos value range for this file is [base...base+size]
size int // file size as provided to AddFile
// lines and infos are protected by mutex
mutex sync.Mutex
lines []int // lines contains the offset of the first character for each line (the first entry is always 0)
infos []lineInfo
}顯而易見，FileSet 可以抽象爲一個存儲 File 的一維數組。而每個 File 的主要組成爲name、base、size。
Position
在go/token中，定義了一個包含具體位置信息的結構，即Position。
type Position struct {
Filename string // filename, if any
Offset int // offset, starting at 0
Line int // line number, starting at 1
Column int // column number, starting at 1 (byte count)
}源代碼中的註釋解釋了各個變量代表的含義，這裏不再贅述。
Lit
BasicLit
BasicLit 是程序代碼中直接表示的值。比如在x*2+1中，2即爲 BasicLit，而x不是 BasicLit 而是 identifier。
literal_beg
// Identifiers and basic type literals
// (these tokens stand for classes of literals)
IDENT // main
INT // 12345
FLOAT // 123.45
IMAG // 123.45i
CHAR // 'a'
STRING // "abc"
literal_end沒有導出的literal_beg和literal_end之間的 Token 都是 BasicLit。
Go 語言的抽象語法樹由go/ast定義。其中ast.BasicLit表示一個基礎類型的面值常量結構，它的定義如下所示。
// A BasicLit node represents a literal of basic type.
BasicLit struct {
ValuePos token.Pos // literal position
Kind token.Token // token.INT, token.FLOAT, token.IMAG, token.CHAR, or token.STRING
Value string // literal string; e.g. 42, 0x7f, 3.14, 1e-9, 2.4i, 'a', '\x7f', "foo" or `\m\n\o`
}ValuePos代表其詞法元素在源代碼中的位置；Kind表示面值的類型；Value表示面值對應的值。
Ident
Ident 同樣位於go/ast中，用於表示標識符類型。
// An Ident node represents an identifier.
Ident struct {
NamePos token.Pos // identifier position
Name string // identifier name
Obj *Object // denoted object; or nil
}NamePos代表其詞法元素在源代碼中的位置；Name表示其標識符的名稱；Obj表示標識符的類型以及其他的一些拓展信息。
ast.Object是一個相對複雜的結構。
// Objects
// An Object describes a named language entity such as a package,
// constant, type, variable, function (incl. methods), or label.
//
// The Data fields contains object-specific data:
//
// Kind Data type Data value
// Pkg *Scope package scope
// Con int iota for the respective declaration
type Object struct {
Kind ObjKind
Name string // declared name
Decl any // corresponding Field, XxxSpec, FuncDecl, LabeledStmt, AssignStmt, Scope; or nil
Data any // object-specific data; or nil
Type any // placeholder for type information; may be nil
}
Expression
Basic Expr
基礎表達式主要是由一元、二元運算符組成的表達式，運算的主題爲各種面值、或標識符。語法如下所示。
Expression = UnaryExpr | Expression binary_op Expression .
UnaryExpr = Operand | unary_op UnaryExpr .
Operand = Literal | identifier | "(" Expression ")" .
binary_op = "||" | "&&" | rel_op | add_op | mul_op .
rel_op = "==" | "!=" | "<" | "<=" | ">" | ">=" .
add_op = "+" | "-" | "|" | "^" .
mul_op = "*" | "/" | "%" | "<<" | ">>" | "&" | "&^" .
unary_op = "+" | "-" | "!" | "^" | "*" | "&" | "<-" .其中 Expression 表示基礎表達式的遞歸定義，可以是 UnaryExpr 類型的一元表達式，或者是 binary_op 生成的二元表達式。而基礎表達式運算符兩邊的對象由 Operand 定義，主要是面值或表達式，也可以是由小括弧包含的表達式。
我們可以使用parser.ParseExpr來解析單個表達式。其返回的值類型實際上是一個抽象類型的接口。
// All expression nodes implement the Expr interface.
type Expr interface {
Node
exprNode()
}其內置了一個ast.Node接口以及一個exprNode方法。
Node 接口僅定義了兩個方法表示了這個語法樹結點的開始位置和結束位置。
// All node types implement the Node interface.
type Node interface {
Pos() token.Pos // position of first character belonging to the node
End() token.Pos // position of first character immediately after the node
}我們可以查詢 go 中 expr 爲後綴的表達式類型。
> go doc go/ast | grep Expr
type BadExpr struct{ ... }
type BinaryExpr struct{ ... }
type CallExpr struct{ ... }
type Expr interface{ ... }
type ExprStmt struct{ ... }
type IndexExpr struct{ ... }
type IndexListExpr struct{ ... }
type KeyValueExpr struct{ ... }
type ParenExpr struct{ ... }
type SelectorExpr struct{ ... }
type SliceExpr struct{ ... }
type StarExpr struct{ ... }
type TypeAssertExpr struct{ ... }
type UnaryExpr struct{ ... }當然表達式類型遠不止這些，這裏僅用作舉例。
我們可以使用ast.BinaryExpr構造一個簡單的二元算術表達式。
func main() {
expr, _ := parser.ParseExpr("1+9*2")
ast.Print(nil, expr)
}輸出結果如下。
0 *ast.BinaryExpr {
1 . X: *ast.BasicLit {
2 . . ValuePos: 1
3 . . Kind: INT
4 . . Value: "1"
5 . }
6 . OpPos: 2
7 . Op: +
8 . Y: *ast.BinaryExpr {
9 . . X: *ast.BasicLit {
10 . . . ValuePos: 3
11 . . . Kind: INT
12 . . . Value: "9"
13 . . }
14 . . OpPos: 4
15 . . Op: *
16 . . Y: *ast.BasicLit {
17 . . . ValuePos: 5
18 . . . Kind: INT
19 . . . Value: "2"
20 . . }
21 . }
22 }相應的樹結構表示：
其中ast.BasicLit是基礎面值類型，ast.BinaryExpr表示二元表達式的結點，其定義如下：
// A BinaryExpr node represents a binary expression.
BinaryExpr struct {
X Expr // left operand
OpPos token.Pos // position of Op
Op token.Token // operator
Y Expr // right operand
}Op代表二元運算符，OpPos代表運算符的位置。X和Y代表二元運算符兩側的操作數，即左值和右值。他們的類型都是Expr這個抽象接口，這就構成了遞歸定義。在上圖中也能看到，ParseExpr得到的結果的最外層是由一個ast.BasicLit和ast.BinaryExpr共同組成的（這也說明了乘法擁有相對較高的優先級）。
File Structure
Go 語言代碼根據目錄組織多個文件，文件必須屬於同一個目錄下。
標準庫go/parser包中的parser.ParseDir用於解析目錄內的全部 Go 語言文件，返回的map[string]*ast.Package包含多個包信息。
ast.Package的結構如下。
// A Package node represents a set of source files
// collectively building a Go package.
type Package struct {
Name string // package name
Scope *Scope // package scope across all files
Imports map[string]*Object // map of package id -> package object
Files map[string]*File // Go source files by filename
}
parser.ParseFile用於解析單個文件，返回的*ast.File包含文件內部代碼信息。
每個*ast.Package是由多個*ast.File文件組成。它們之間的邏輯關係如下圖所示：
ast.File結構如下所示。
type File struct {
Doc *CommentGroup // associated documentation; or nil
Package token.Pos // position of "package" keyword
Name *Ident // package name
Decls []Decl // top-level declarations; or nil
Scope *Scope // package scope (this file only)
Imports []*ImportSpec // imports in this file
Unresolved []*Ident // unresolved identifiers in this file
Comments []*CommentGroup // list of all comments in the source file
}
File.Name成員表示文件對應包的名字；File.Imports表示當前文件導入的第三方的包信息；File.Decls包含了當前文件全部的包級聲明信息（包含導入信息），這意味着即使沒有File.Imports，我們也能夠從File.Decls中獲取所有的包級信息。
我們可以通過File.Decls查看每個成員的類型。
/*
package main
import "go/ast"
import "go/parser"
type intArray [10]int
const hello = "hello world!"
var array = []int{1, 2, 3, 4, 5}
func main() {
var a ast.File
a.Pos()
}
*/
for idx, decl := range pl.Decls {
fmt.Printf("%d: %T\n", idx, decl)
}
/*
0: *ast.GenDecl
1: *ast.GenDecl
2: *ast.GenDecl
3: *ast.GenDecl
4: *ast.GenDecl
5: *ast.FuncDecl
*/
我們可以發現import、type、const和var都是對應*ast.GenDecl類型，只有函數是獨立的*ast.FuncDecl類型。
General declaration
通用聲明是不含函數聲明的包級別聲明，包含：導入、類型、常量和變量四種聲明。
Import
在 Go 中，當 package 關鍵字定義一個包後，導入語句必須其後出現，然後才能是類型、常量等其他聲明。
根據導入語法定義，創建的導入聲明有以下幾種形式
import "fmt"
import https "net/http"
import . "go/token"
import _ "go/parser"第一種爲默認的導包形式，即將包名作爲符號導入當前的文件的符號空間；第二種將導入的net/http以https命名導入當前文件的符號空間；第三種將包中所有公開符號導入當前文件的符號空間；第四種僅觸發包初始化動作，而不導入任何符號。
我們可以解析四種不同的導入方式來查看其中的異同。
func main() {
var src string = `package main
import "fmt"
import https "net/http"
import . "go/token"
import _ "go/parser"`
fl := token.NewFileSet()
pl, _ := parser.ParseFile(fl, "example.go", src, parser.ImportsOnly)
for idx, spec := range pl.Imports {
fmt.Printf("%d\t %s\t %#v\n", idx, spec.Name, spec.Path)
}
}
/*
0 <nil> &ast.BasicLit{ValuePos:22, Kind:9, Value:"\"fmt\""}
1 https &ast.BasicLit{ValuePos:41, Kind:9, Value:"\"net/http\""}
2 . &ast.BasicLit{ValuePos:61, Kind:9, Value:"\"go/token\""}
3 _ &ast.BasicLit{ValuePos:81, Kind:9, Value:"\"go/parser\""}
*/
Type
類型聲明在語法樹的結點類型爲ast.TypeSpec。我們可以通過以下代碼查看類型聲明列表中的每個元素。
func main() {
var src string = `package main
type b string
type array [10]int`
fl := token.NewFileSet()
pl, _ := parser.ParseFile(fl, "example.go", src, parser.AllErrors)
for idx, spec := range pl.Decls {
if v, ok := spec.(*ast.GenDecl); ok {
fmt.Printf("%d\t %T\t %#v\n", idx, v, v.Specs)
}
}
}
/*
0 *ast.GenDecl []ast.Spec{(*ast.TypeSpec)(0x14000122080)}
1 *ast.GenDecl []ast.Spec{(*ast.TypeSpec)(0x14000122100)}
*/
ast.TypeSpec的結構定義如下。
// A TypeSpec node represents a type declaration (TypeSpec production).
TypeSpec struct {
Doc *CommentGroup // associated documentation; or nil
Name *Ident // type name
TypeParams *FieldList // type parameters; or nil
Assign token.Pos // position of '=', if any
Type Expr // *Ident, *ParenExpr, *SelectorExpr, *StarExpr, or any of the *XxxTypes
Comment *CommentGroup // line comments; or nil
}Name表示類型定義的名稱；Assign對應=符號的位置。如果Assign對應的位置有效，表示這是定義已有類型的一個別名；Type表示具體的類型的表達式。
Const
在 Go 中，我們擁有兩種常量：弱類型常量和強類型常量。
const Pi = 3.14
const Pi64 float64 = 3.1415926其中 Pi 被定義爲弱類型的浮點數常量，可以賦值給 float32 或 float64 爲基礎其它變量。而 Pi64 是被定義爲 float64 的強類型常量，默認只能非接受 float64 類型的變量賦值。
常量聲明和導入聲明一樣同屬ast.GenDecl類型的通用聲明，它們的區別在於ast.GenDecl.Specs部分。我們可以使用同樣的代碼查看常量聲明語句中 Specs 中元素的類型。
func main() {
var src string = `package main
const Pi = 3.14
const Pi64 float64 = 3.1415926
`
fl := token.NewFileSet()
pl, _ := parser.ParseFile(fl, "example.go", src, parser.AllErrors)
for idx, spec := range pl.Decls {
if v, ok := spec.(*ast.GenDecl); ok {
fmt.Printf("%d\t %T\t %#v\n", idx, v, v.Specs)
}
}
}
/*
0 *ast.GenDecl []ast.Spec{(*ast.ValueSpec)(0x1400010c0a0)}
1 *ast.GenDecl []ast.Spec{(*ast.ValueSpec)(0x1400010c0f0)}
*/
可以看到常量類型爲ast.ValueSpec。其結構如下所示。
ValueSpec struct {
Doc *CommentGroup // associated documentation; or nil
Names []*Ident // value names (len(Names) > 0)
Type Expr // value type; or nil
Values []Expr // initial values; or nil
Comment *CommentGroup // line comments; or nil
}進一步的，我們可以使用ast.Print(nil, v.Specs)來查看兩者異同。
0 []ast.Spec (len = 1) {
1 . 0: *ast.ValueSpec {
2 . . Names: []*ast.Ident (len = 1) {
3 . . . 0: *ast.Ident {
4 . . . . NamePos: 20
5 . . . . Name: "Pi"
6 . . . . Obj: *ast.Object {
7 . . . . . Kind: const
8 . . . . . Name: "Pi"
9 . . . . . Decl: *(obj @ 1)
10 . . . . . Data: 0
11 . . . . }
12 . . . }
13 . . }
14 . . Values: []ast.Expr (len = 1) {
15 . . . 0: *ast.BasicLit {
16 . . . . ValuePos: 25
17 . . . . Kind: FLOAT
18 . . . . Value: "3.14"
19 . . . }
20 . . }
21 . }
22 }
0 []ast.Spec (len = 1) {
1 . 0: *ast.ValueSpec {
2 . . Names: []*ast.Ident (len = 1) {
3 . . . 0: *ast.Ident {
4 . . . . NamePos: 36
5 . . . . Name: "Pi64"
6 . . . . Obj: *ast.Object {
7 . . . . . Kind: const
8 . . . . . Name: "Pi64"
9 . . . . . Decl: *(obj @ 1)
10 . . . . . Data: 0
11 . . . . }
12 . . . }
13 . . }
14 . . Type: *ast.Ident {
15 . . . NamePos: 41
16 . . . Name: "float64"
17 . . }
18 . . Values: []ast.Expr (len = 1) {
19 . . . 0: *ast.BasicLit {
20 . . . . ValuePos: 51
21 . . . . Kind: FLOAT
22 . . . . Value: "3.1415926"
23 . . . }
24 . . }
25 . }
26 }可以發現相較於弱類型常量，強類型常量的定義擁有了Type屬性，使用ast.Ident標記了常量的類型。
Var
我們同樣可以使用先前的例子，看到其中的異同。
0 []ast.Spec (len = 1) {
1 . 0: *ast.ValueSpec {
2 . . Names: []*ast.Ident (len = 1) {
3 . . . 0: *ast.Ident {
4 . . . . NamePos: 18
5 . . . . Name: "Pi"
6 . . . . Obj: *ast.Object {
7 . . . . . Kind: var
8 . . . . . Name: "Pi"
9 . . . . . Decl: *(obj @ 1)
10 . . . . . Data: 0
11 . . . . }
12 . . . }
13 . . }
14 . . Values: []ast.Expr (len = 1) {
15 . . . 0: *ast.BasicLit {
16 . . . . ValuePos: 23
17 . . . . Kind: FLOAT
18 . . . . Value: "3.14"
19 . . . }
20 . . }
21 . }
22 }
0 []ast.Spec (len = 1) {
1 . 0: *ast.ValueSpec {
2 . . Names: []*ast.Ident (len = 1) {
3 . . . 0: *ast.Ident {
4 . . . . NamePos: 32
5 . . . . Name: "Pi64"
6 . . . . Obj: *ast.Object {
7 . . . . . Kind: var
8 . . . . . Name: "Pi64"
9 . . . . . Decl: *(obj @ 1)
10 . . . . . Data: 0
11 . . . . }
12 . . . }
13 . . }
14 . . Type: *ast.Ident {
15 . . . NamePos: 37
16 . . . Name: "float64"
17 . . }
18 . . Values: []ast.Expr (len = 1) {
19 . . . 0: *ast.BasicLit {
20 . . . . ValuePos: 47
21 . . . . Kind: FLOAT
22 . . . . Value: "3.1415926"
23 . . . }
24 . . }
25 . }
26 }可以看到變量聲明幾乎與常量聲明相同。但我們仍可以通過ast.GenDecl.Tok來區分它們。
/*
package main
var Pi = 3.14
const cPi = 3.14
*/
fmt.Printf("%s\t %#v\n", v.Tok, v.Specs)
/*
var []ast.Spec{(*ast.ValueSpec)(0x140001000a0)}
const []ast.Spec{(*ast.ValueSpec)(0x140001000f0)}
*/
Vars
Go 中有如下定義方式，暫且稱爲分組定義。
var (
a = 1
b = 2
c = 3
d = "4"
)當我們使用先前的例子進行解析，其與 Var 的區別僅在於[]ast.Spec的成員隨之增加。
fmt.Printf("%d\n", len(v.Specs))
// 4Function
一個完整的函數定義如下。
func (p *xType) Hello(arg1, arg2 int) (bool, error) { ... }函數的聲明對應ast.FuncDecl，它的定義如下所示。
// A FuncDecl node represents a function declaration.
FuncDecl struct {
Doc *CommentGroup // associated documentation; or nil
Recv *FieldList // receiver (methods); or nil (functions)
Name *Ident // function/method name
Type *FuncType // function signature: type and value parameters, results, and position of "func" keyword
Body *BlockStmt // function body; or nil for external (non-Go) function
}Recv對應接收者列表，在這裏代表(p *xType)部分；Name是函數的名字，這裏的名字是Hello；Type表示方法或函數的類型（函數的類型和接口的定義一致，因爲接口並不包含接收者信息），其中包含輸入參數和返回值信息；Body表示函數體中的語句部分。
函數聲明最重要的是Name、Recv、輸入參數和返回值（FuncType），其中除Name之外的三者實際上都是ast.FieldList類型，輸入參數和返回值被封裝爲ast.FuncType類型。表示函數類型的ast.FuncType結構體定義如下：
// A FuncType node represents a function type.
FuncType struct {
Func token.Pos // position of "func" keyword (token.NoPos if there is no "func")
TypeParams *FieldList // type parameters; or nil
Params *FieldList // (incoming) parameters; non-nil
Results *FieldList // (outgoing) results; or nil
}Params和Results分別表示輸入參數和返回值列表，它們和函數的接收者參數列表都是ast.FieldList類型。
下面是ast.FielfList的結構。
// A FieldList represents a list of Fields, enclosed by parentheses,
// curly braces, or square brackets.
type FieldList struct {
Opening token.Pos // position of opening parenthesis/brace/bracket, if any
List []*Field // field list; or nil
Closing token.Pos // position of closing parenthesis/brace/bracket, if any
}其中包含了一個元素類型爲ast.Field的切片，增加了開始與結束的位置信息。
ast.Field的結構如下所示。
type Field struct {
Doc *CommentGroup // associated documentation; or nil
Names []*Ident // field/method/(type) parameter names; or nil
Type Expr // field/method/parameter type; or nil
Tag *BasicLit // field tag; or nil
Comment *CommentGroup // line comments; or nil
}Name 存放參數的標識符；Type 表示這一組參數的類型。
假定有如下函數定義：
func Hello(s0, s1 string, s2 string)則s0, s1爲同一個類型定義，對應一個ast.Field，s2則對應另一個ast.Field。
下面是一個簡單的例子。
假定有如下方法函數
func (*int) gogogo(arg1, arg2 int, arg3 string) int { return arg1 + arg2; }我們可以使用以下的一個例子解析：
func main() {
var src string = `package main
func (*int) gogogo(arg1, arg2 int, arg3 string) int { return arg1 + arg2; }
`
fl := token.NewFileSet()
pl, _ := parser.ParseFile(fl, "example.go", src, parser.AllErrors)
for _, spec := range pl.Decls {
if v, ok := spec.(*ast.FuncDecl); ok {
ast.Print(nil, v)
}
}
}
得到的結果
0 *ast.FuncDecl {
1 . Recv: *ast.FieldList {
2 . . Opening: 19
3 . . List: []*ast.Field (len = 1) {
4 . . . 0: *ast.Field {
5 . . . . Type: *ast.StarExpr {
6 . . . . . Star: 20
7 . . . . . X: *ast.Ident {
8 . . . . . . NamePos: 21
9 . . . . . . Name: "int"
10 . . . . . }
11 . . . . }
12 . . . }
13 . . }
14 . . Closing: 24
15 . }
16 . Name: *ast.Ident {
17 . . NamePos: 26
18 . . Name: "gogogo"
19 . }
20 . Type: *ast.FuncType {
21 . . Func: 14
22 . . Params: *ast.FieldList {
23 . . . Opening: 32
24 . . . List: []*ast.Field (len = 2) {
25 . . . . 0: *ast.Field {
26 . . . . . Names: []*ast.Ident (len = 2) {
27 . . . . . . 0: *ast.Ident {
28 . . . . . . . NamePos: 33
29 . . . . . . . Name: "arg1"
30 . . . . . . . Obj: *ast.Object {
31 . . . . . . . . Kind: var
32 . . . . . . . . Name: "arg1"
33 . . . . . . . . Decl: *(obj @ 25)
34 . . . . . . . }
35 . . . . . . }
36 . . . . . . 1: *ast.Ident {
37 . . . . . . . NamePos: 39
38 . . . . . . . Name: "arg2"
39 . . . . . . . Obj: *ast.Object {
40 . . . . . . . . Kind: var
41 . . . . . . . . Name: "arg2"
42 . . . . . . . . Decl: *(obj @ 25)
43 . . . . . . . }
44 . . . . . . }
45 . . . . . }
46 . . . . . Type: *ast.Ident {
47 . . . . . . NamePos: 44
48 . . . . . . Name: "int"
49 . . . . . }
50 . . . . }
51 . . . . 1: *ast.Field {
52 . . . . . Names: []*ast.Ident (len = 1) {
53 . . . . . . 0: *ast.Ident {
54 . . . . . . . NamePos: 49
55 . . . . . . . Name: "arg3"
56 . . . . . . . Obj: *ast.Object {
57 . . . . . . . . Kind: var
58 . . . . . . . . Name: "arg3"
59 . . . . . . . . Decl: *(obj @ 51)
60 . . . . . . . }
61 . . . . . . }
62 . . . . . }
63 . . . . . Type: *ast.Ident {
64 . . . . . . NamePos: 54
65 . . . . . . Name: "string"
66 . . . . . }
67 . . . . }
68 . . . }
69 . . . Closing: 60
70 . . }
71 . . Results: *ast.FieldList {
72 . . . Opening: 0
73 . . . List: []*ast.Field (len = 1) {
74 . . . . 0: *ast.Field {
75 . . . . . Type: *ast.Ident {
76 . . . . . . NamePos: 62
77 . . . . . . Name: "int"
78 . . . . . }
79 . . . . }
80 . . . }
81 . . . Closing: 0
82 . . }
83 . }
84 . Body: *ast.BlockStmt {
85 . . Lbrace: 66
86 . . List: []ast.Stmt (len = 1) {
87 . . . 0: *ast.ReturnStmt {
88 . . . . Return: 68
89 . . . . Results: []ast.Expr (len = 1) {
90 . . . . . 0: *ast.BinaryExpr {
91 . . . . . . X: *ast.Ident {
92 . . . . . . . NamePos: 75
93 . . . . . . . Name: "arg1"
94 . . . . . . . Obj: *(obj @ 30)
95 . . . . . . }
96 . . . . . . OpPos: 80
97 . . . . . . Op: +
98 . . . . . . Y: *ast.Ident {
99 . . . . . . . NamePos: 82
100 . . . . . . . Name: "arg2"
101 . . . . . . . Obj: *(obj @ 39)
102 . . . . . . }
103 . . . . . }
104 . . . . }
105 . . . }
106 . . }
107 . . Rbrace: 88
108 . }
109 }下面來分析ast.BlockStmt，其結構如下所示。
// A BlockStmt node represents a braced statement list.
BlockStmt struct {
Lbrace token.Pos // position of "{"
List []Stmt
Rbrace token.Pos // position of "}", if any (may be absent due to syntax error)
}ast.BlockStmt中包含塊的起始位置，以及類型爲ast.Stmt的切片。實質上ast.BlockStmt僅僅只是簡單包裝了[]ast.Stmt。
ast.Stmt是一個抽象類型的接口。函數體中的語句塊構成的語法樹和類型中的語法樹結構很相似，但是語句的語法樹最大的特點是可以循環遞歸定義，而類型的語法樹不能遞歸定義自身（語義層面禁止）。
// All statement nodes implement the Stmt interface.
type Stmt interface {
Node
stmtNode()
}我們也可以查找 Stmt 爲後綴的表達式類型。
> go doc go/ast | grep Stmt
type AssignStmt struct{ ... }
type BadStmt struct{ ... }
type BlockStmt struct{ ... }
type BranchStmt struct{ ... }
type DeclStmt struct{ ... }
type DeferStmt struct{ ... }
type EmptyStmt struct{ ... }
type ExprStmt struct{ ... }
type ForStmt struct{ ... }
type GoStmt struct{ ... }
type IfStmt struct{ ... }
type IncDecStmt struct{ ... }
type LabeledStmt struct{ ... }
type RangeStmt struct{ ... }
type ReturnStmt struct{ ... }
type SelectStmt struct{ ... }
type SendStmt struct{ ... }
type Stmt interface{ ... }
type SwitchStmt struct{ ... }
type TypeSwitchStmt struct{ ... }Pointer
Go 語言指針類型的語法規範：
PointerType = "*" BaseType .
BaseType = Type .
Type = TypeName | TypeLit | "(" Type ")" .
...在 Go 語言中，指針類型以星號*開頭，後面是 BaseType 定義的類型表達式。從語法規範角度看，Go 語言沒有單獨定義多級指針，只有一種指向 BaseType 類型的一級指針。但是 PointerType 又可以作爲 TypeLit 類型面值被重新用作 BaseType，這就產生了多級指針的語法。
首先來看一下一級指針的 AST
func main() {
var src string = `package main
type IntPtr *int
`
fl := token.NewFileSet()
pl, _ := parser.ParseFile(fl, "example.go", src, parser.AllErrors)
for _, spec := range pl.Decls {
if v, ok := spec.(*ast.GenDecl); ok {
ast.Print(nil, v)
}
}
}
其結果爲：
0 *ast.GenDecl {
1 . TokPos: 14
2 . Tok: type
3 . Lparen: 0
4 . Specs: []ast.Spec (len = 1) {
5 . . 0: *ast.TypeSpec {
6 . . . Name: *ast.Ident {
7 . . . . NamePos: 19
8 . . . . Name: "IntPtr"
9 . . . . Obj: *ast.Object {
10 . . . . . Kind: type
11 . . . . . Name: "IntPtr"
12 . . . . . Decl: *(obj @ 5)
13 . . . . }
14 . . . }
15 . . . Assign: 0
16 . . . Type: *ast.StarExpr {
17 . . . . Star: 21
18 . . . . X: *ast.Ident {
19 . . . . . NamePos: 22
20 . . . . . Name: "int"
21 . . . . }
22 . . . }
23 . . }
24 . }
25 . Rparen: 0
26 }能看到指針所使用的類型爲ast.StarExpr。其結構如下所示。
StarExpr struct {
Star token.Pos // position of "*"
X Expr // operand
}Star 表示*所在的位置，X 指向一個遞歸定義的類型表達式。
指針是一種天然遞歸定義的類型。我們可以再定義一個指向 IntPtr 類型的指針，即指向 int 的二級指針。
相同的辦法得到type IntPtrPtr **int的 AST：
0 *ast.GenDecl {
1 . TokPos: 14
2 . Tok: type
3 . Lparen: 0
4 . Specs: []ast.Spec (len = 1) {
5 . . 0: *ast.TypeSpec {
6 . . . Name: *ast.Ident {
7 . . . . NamePos: 19
8 . . . . Name: "IntPtrPtr"
9 . . . . Obj: *ast.Object {
10 . . . . . Kind: type
11 . . . . . Name: "IntPtrPtr"
12 . . . . . Decl: *(obj @ 5)
13 . . . . }
14 . . . }
15 . . . Assign: 0
16 . . . Type: *ast.StarExpr {
17 . . . . Star: 29
18 . . . . X: *ast.StarExpr {
19 . . . . . Star: 30
20 . . . . . X: *ast.Ident {
21 . . . . . . NamePos: 31
22 . . . . . . Name: "int"
23 . . . . . }
24 . . . . }
25 . . . }
26 . . }
27 . }
28 . Rparen: 0
29 }可以看到 IntPtrPtr 與 IntPtr 解析的差別在於嵌套了另一個ast.StarExpr，對於多級指針而言，其 AST 很像一個單向鏈表。其中 X 成員指向的是減一級指針的*ast.StarExpr結點，鏈表的尾結點是一個*ast.Ident標識符類型。
Array
在傳統的 C/C++ 中，數組是和指針近似等同的類型。在傳遞參數是我們可以通過傳遞標識符，即數組的首地址。但在 Go 中，我們傳遞標識符得到的卻是傳遞參數的值拷貝。
其語法定義如下所示。
ArrayType = "[" ArrayLength "]" ElementType .
ArrayLength = Expression .
ElementType = Type .我們定義一個簡單的數組
其 AST 表現爲：
0 *ast.GenDecl {
1 . TokPos: 14
2 . Tok: type
3 . Lparen: 0
4 . Specs: []ast.Spec (len = 1) {
5 . . 0: *ast.TypeSpec {
6 . . . Name: *ast.Ident {
7 . . . . NamePos: 19
8 . . . . Name: "array"
9 . . . . Obj: *ast.Object {
10 . . . . . Kind: type
11 . . . . . Name: "array"
12 . . . . . Decl: *(obj @ 5)
13 . . . . }
14 . . . }
15 . . . Assign: 0
16 . . . Type: *ast.ArrayType {
17 . . . . Lbrack: 25
18 . . . . Len: *ast.BasicLit {
19 . . . . . ValuePos: 26
20 . . . . . Kind: INT
21 . . . . . Value: "10"
22 . . . . }
23 . . . . Elt: *ast.Ident {
24 . . . . . NamePos: 29
25 . . . . . Name: "int"
26 . . . . }
27 . . . }
28 . . }
29 . }
30 . Rparen: 0
31 }其ast.TypeSpec.Type爲ast.ArrayType，其結構如下所示。
ArrayType struct {
Lbrack token.Pos // position of "["
Len Expr // Ellipsis node for [...]T array types, nil for slice types
Elt Expr // element type
}Len是一個表示數組長度的表達式，正如註釋中所提到的，其表達式也可以是...表示從元素個數提取長度；數組的元素類型由Elt定義，其值對應一個類型的表達式。和指針類似，數組類型同樣可以遞歸定義。因此我們有了二維數組甚至多維數組。
我們定義一個二維數組：
其 AST 表現如下：
0 *ast.GenDecl {
1 . TokPos: 14
2 . Tok: type
3 . Lparen: 0
4 . Specs: []ast.Spec (len = 1) {
5 . . 0: *ast.TypeSpec {
6 . . . Name: *ast.Ident {
7 . . . . NamePos: 19
8 . . . . Name: "arrays"
9 . . . . Obj: *ast.Object {
10 . . . . . Kind: type
11 . . . . . Name: "arrays"
12 . . . . . Decl: *(obj @ 5)
13 . . . . }
14 . . . }
15 . . . Assign: 0
16 . . . Type: *ast.ArrayType {
17 . . . . Lbrack: 26
18 . . . . Len: *ast.BasicLit {
19 . . . . . ValuePos: 27
20 . . . . . Kind: INT
21 . . . . . Value: "4"
22 . . . . }
23 . . . . Elt: *ast.ArrayType {
24 . . . . . Lbrack: 29
25 . . . . . Len: *ast.BasicLit {
26 . . . . . . ValuePos: 30
27 . . . . . . Kind: INT
28 . . . . . . Value: "5"
29 . . . . . }
30 . . . . . Elt: *ast.Ident {
31 . . . . . . NamePos: 32
32 . . . . . . Name: "int"
33 . . . . . }
34 . . . . }
35 . . . }
36 . . }
37 . }
38 . Rparen: 0
39 }ast.TypeSpec.Type.Elt.Elt不再是ast.Ident而是嵌套了一個ast.ArrayType。由此可見，數組類型的 AST 也可以類似的視作一個單向鏈表結構。後N-1維的數組的元素是*ast.ArrayType類型，最後的尾結點對應一個*ast.Ident標識符（也可以是其它面值類型）。
Slice
Go 語言中切片是簡化的數組，從其語法定義上來看，切片與數組的區別僅僅在於切片省略了數組的長度。其語法定義如下：
SliceType = "[" "]" ElementType .
ElementType = Type .以簡單的切片爲例：
其 AST 表現如下：
0 *ast.GenDecl {
1 . TokPos: 14
2 . Tok: type
3 . Lparen: 0
4 . Specs: []ast.Spec (len = 1) {
5 . . 0: *ast.TypeSpec {
6 . . . Name: *ast.Ident {
7 . . . . NamePos: 19
8 . . . . Name: "s"
9 . . . . Obj: *ast.Object {
10 . . . . . Kind: type
11 . . . . . Name: "s"
12 . . . . . Decl: *(obj @ 5)
13 . . . . }
14 . . . }
15 . . . Assign: 0
16 . . . Type: *ast.ArrayType {
17 . . . . Lbrack: 21
18 . . . . Elt: *ast.Ident {
19 . . . . . NamePos: 23
20 . . . . . Name: "int"
21 . . . . }
22 . . . }
23 . . }
24 . }
25 . Rparen: 0
26 }通過 AST，我們能看到切片與數組的區別在於，在切片中其ast.ArrayType.Len的值變爲了nil，即切片的Len爲nil，數組的Len爲一個基本面值。
Others
Go AST 的組成遠不止如此，其中還有大量的複合類型，複合面值、複合表達式、語句塊和語句等未曾提及釋義。但相信通過動手實踐，我們的認知並不會止步於此。
AST explorer
Go 是靜態語言，我們必須將其編譯而後執行，這意味着我們無法實時得到我們想要的結果。這對我們使用 Go AST 進行調試、分析造成了阻礙。
AST explorer 是一個 AST 可視化工具網站，其支持對多個語言進行解析，Go 也不例外。通過 AST explorer，我們可以快速瞭解其 AST 組成，方便我們進行調試、分析。
網鼎杯 2022 某賽道 Handmake
介紹了那麼多關於 Go AST，下面就是實際的運用。
拿到的文件是一個 go 源碼，其對標識符、語句等進行了大量混淆。
我們從程序入口着手分析。
func main() {
var nFAzj, CuSkl string
jjxXf := []byte{
37, 73, 151, 135, 65, 58, 241, 90, 33, 86, 71, 41, 102, 241, 213, 234, 67, 144, 139, 20, 112, 150, 41, 7, 158, 251, 167, 249, 24, 129, 72, 64, 83, 142, 166, 236, 67, 18, 211, 100, 91, 38, 83, 147, 40, 78, 239, 113, 232, 83, 227, 47, 192, 227, 70, 167, 201, 249, 156, 101, 216, 159, 116, 210, 152, 234, 38, 145, 198, 58, 24, 183, 72, 143, 136, 234, 246}
KdlaH := []byte{
191, 140, 114, 245, 142, 55, 190, 30, 161, 18, 200, 7, 21, 59, 17, 44, 34, 181, 109, 116, 146, 145, 189, 68, 142, 113, 0, 33, 46, 184, 21, 33, 66, 99, 124, 167, 201, 88, 133, 20, 211, 67, 133, 250, 62, 28, 138, 229, 105, 102, 125, 124, 208, 180, 50, 146, 67, 39, 55, 240, 239, 203, 230, 142, 20, 90, 205, 27, 128, 136, 151, 140, 222, 92, 152, 1, 222, 138, 254, 246, 223, 224, 236, 33, 60, 170, 189, 77, 124, 72, 135, 46, 235, 17, 32, 28, 245}
fmt.Print(MPyt9GWTRfAFNvb1(jjxXf))
fmt.Scanf("%20s", &nFAzj)
fmt.Print(kZ2BFvOxepd5ALDR(KdlaH))
fmt.Scanf("%20s", &CuSkl)
vNvUO := GwSqNHQ7dPXpIG64(nFAzj)
YJCya := ""
mvOxK := YI3z8ZxOKhfLmTPC(CuSkl)
if mvOxK != nil {
YJCya = mvOxK()
}
if YJCya != "" && vNvUO != "" {
fmt.Printf("flag{%s%s}\n", vNvUO, YJCya)
}
}此時我們有兩種選擇瞭解程序邏輯：
- 編譯源文件，通過編譯器優化得到一個化簡的二進制文件而後運行、分析。
- 摘取片段代碼，而後執行片段。
目前爲止，兩者都是可行的。但前者需要大量的系統資源，並需要一定時間；後者需要考慮到函數間的引用鏈。
不管何種方式，我們都能得到fmt.Print打印的明文內容：
Input the first function, which has 6 parameters and the third named gLIhR:
Input the second function, which has 3 callers and invokes the function named cHZv5op8rOmlAkb6:顯而易見，出題人並不希望我們通過編譯優化的方式解題，而是通過分析源代碼得到信息。
到這裏，我們就可以藉助 Go AST 來幫助我們分析得到這類信息。
Part 1
首先考慮解決第一個問題：Input the first function, which has 6 parameters and the third named gLIhR:
提取出要求：
- 函數有 6 個參數
- 第 3 個參數名稱爲
gLIhR
通過ast.Inspect遍歷函數定義節點，我們可以迅速找到對應的函數名。
func solve_part1(n *ast.File) {
ast.Inspect(n, func(node ast.Node) bool {
switch x := node.(type) {
case *ast.FuncDecl:
paramLen := 0
funcName := x.Name.Name
thirdParamName := ""
for _, param := range x.Type.Params.List {
for _, name := range param.Names {
paramLen += 1
if paramLen == 3 {
thirdParamName = name.Name
}
}
}
if paramLen == 6 && thirdParamName == "gLIhR" {
fmt.Println("find part 1:", funcName)
}
}
return true
})
}
func main() {
src, _ := os.ReadFile("challenge.go")
fl := token.NewFileSet()
pl, _ := parser.ParseFile(fl, "challenge.go", src, parser.AllErrors)
solve_part1(pl)
}
// find part1: ZlXDJkH3OZN4Mayd由此，我們得到了第一個答案：ZlXDJkH3OZN4Mayd
Part 2
第二個問題：Input the second function, which has 3 callers and invokes the function named cHZv5op8rOmlAkb6:
提取出要求：
- 函數擁有三個調用者
- 並且函數調用了
cHZv5op8rOmlAkb6方法
由於 Go AST 沒有設計直接獲取引用的 API，我們需要手動實現一個Visitor獲取引用信息。
func solve_part2(n *ast.File) {
type Info struct {
start int
end int
referenceFuncs *[]string
references int // 被引用的次數
}
InfoArray := map[string]Info{}
// 初始化函數map
ast.Inspect(n, func(node ast.Node) bool {
switch x := node.(type) {
case *ast.FuncDecl:
funcName := x.Name.Name
info := Info{references: 0, referenceFuncs: new([]string), start: int(x.Body.Lbrace), end: int(x.Body.Rbrace)}
InfoArray[funcName] = info
}
return true
})
// 獲取調用信息
ast.Inspect(n, func(node ast.Node) bool {
switch x := node.(type) {
case *ast.CallExpr:
if ident, ok := x.Fun.(*ast.Ident); ok {
funcName := ""
callName := ident.Name
if callName == "string" || callName == "make" {
return true
}
var info Info
// 尋找調用callFunc的函數
for key, info := range InfoArray {
if info.start < int(ident.Pos()) && info.end > int(ident.End()) {
funcName = key
}
}
// set references
info = InfoArray[callName]
info.references++
InfoArray[callName] = info
// set referenceFuncs
*InfoArray[funcName].referenceFuncs = append(*InfoArray[funcName].referenceFuncs, callName)
}
}
return true
})
// 搜索符合條件的函數
for key, info := range InfoArray {
if info.references == 3 {
for _, s := range *info.referenceFuncs {
if s == "cHZv5op8rOmlAkb6" {
fmt.Println("find part 2:", key)
}
}
}
}
}
func main() {
src, _ := os.ReadFile("challenge.go")
fl := token.NewFileSet()
pl, _ := parser.ParseFile(fl, "challenge.go", src, parser.AllErrors)
solve_part2(pl)
}
// find part 2: UhnCm82SDGE0zLYO最終得到了第二部分的答案：UhnCm82SDGE0zLYO
最後，我們只需要將代碼片段截取，執行程序邏輯就能得到正確的答案。
func GwSqNHQ7dPXpIG64(cJPTR string) string {
YrXQd := hex.EncodeToString([]byte(cJPTR))
return fmt.Sprintf("%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c", YrXQd[22], YrXQd[19], YrXQd[20], YrXQd[21], YrXQd[28], YrXQd[10], YrXQd[20], YrXQd[7], YrXQd[29], YrXQd[14], YrXQd[0], YrXQd[18], YrXQd[3], YrXQd[24], YrXQd[27], YrXQd[31])
}
func cHZv5op8rOmlAkb6(HIGXt []byte, VGvny string, ZOkKV string, eU0uD string) string {
QTk4l := make([]byte, 20)
Ek08m := [16]byte{
167, 238, 45, 89, 160, 95, 34, 175, 158, 169, 20, 217, 68, 137, 231, 54}
for i := 0; i < 16; i++ {
QTk4l[i] += Ek08m[i] ^ HIGXt[i]
}
return string(QTk4l)
}
func UhnCm82SDGE0zLYO() string {
SythK := []byte{
159, 141, 72, 106, 196, 62, 16, 205, 170, 159, 36, 232, 125, 239, 208, 3}
var Vw2mJ, Nij87, zVclR string
return cHZv5op8rOmlAkb6(SythK, Vw2mJ, Nij87, zVclR)
}
func getflag() {
nFAzj := "ZlXDJkH3OZN4Mayd"
vNvUO := GwSqNHQ7dPXpIG64(nFAzj)
YJCya := UhnCm82SDGE0zLYO()
fmt.Printf("flag{%s%s}\n", vNvUO, YJCya)
}總結
本文簡要介紹了 Go AST 的結構以及組成，雖然其中仍有大量未列出的表達式類型、語句類型、複雜類型等，但通過這篇文章的梳理以及介紹，我們能夠了解到如何瞭解 Go AST，正所謂授人以魚不如授人以漁，只有學會如何學習 Go AST，才能真正瞭解到 Go AST 的魅力。
而對於例舉題目而言，其難度仍有拓展空間，例如利用大量的無意義函數引用，膨脹源碼等操作，使分析難度加大，將暴力分析的可行性排除在外，不乏爲一個較好的出題方向。
Reference
The Go Programming Language
Go 語言定製指南
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://tttang.com/archive/1736/