A growing trend in compiler design is to enable modular extensions to intermediate representations (IRs).
Multi-Level Intermediate Representation (MLIR) is a new effort to enable faster compiler development by providing an extensible framework for downstream developers to define custom IRs with MLIR dialects.
Sets of MLIR dialects define new IRs that are tailored for specific domains.
The diversity and rapid evolution of these IRs make it impractical to pre-define custom test generator logic for every available dialect.

We design a new approach called  that automatically infers and applies custom mutations from existing tests.
The key essence of  is that inferred custom mutations are parameterized and context-dependent such that they can be concretized differently depending on the target context.
By doing this, we obviate the need to manually write custom mutations for newly introduced MLIR dialects.
Further,  increases the chance of finding effective edit locations and reduces the chance of inserting invalid edit content by performing $k$-ancestor-prefix and $l$-sibling-postfix matching.

We compare  to three baselines: Grammarinator—a grammar-based fuzzer without custom mutators, MLIRSmith—a custom test generator for MLIR, and NeuRI—a custom test generator with support for parameterized generation.
We conduct this comprehensive comparison on 4 different MLIR projects where each project defines a new set of MLIR dialects that would take months of effort to manually write custom input generation and mutation logic.
Our evaluation shows that  on average improves input diversity by , which increases branch coverage by .
Further, we show that our context dependent custom mutation increases the proportion of valid tests by up to ,
indicating that  correctly concretizes its parameterized mutations with respect to the target context.
Parameterization of the mutations reduces the fraction of tests violating general MLIR constraints by , increasing the time spent fuzzing dialect-specific code.

MLIR, grammar-based fuzzing, code patterns, program transformation

§ INTRODUCTION

A common compiler design consists of three components—a frontend, an optimizer, and a backend [1] where the frontend translates source code to an intermediate representation (IR), the optimizer performs optimizations on the IR, and the backend translates the IR into instructions specific to the target architecture.
The LLVM project lowered the barrier to entry by providing a common LLVM intermediate representation with different architecture backends.

There is a growing trend to advance modular compiler design through extensible infrastructure for intermediate representations (IR).
Multi-Level Intermediate Representation (MLIR) is one such effort.
It aims to create a unified infrastructure for manipulating an extensible IR format, enabling reusable compiler components.
Unlike LLVM, which defines a single common intermediate representation (IR), MLIR enables developers to extend the underlying IR through the concept of MLIR dialects.
Each MLIR dialect essentially defines a new IR consisting of a unique set of operations, types, and attributes with domain-specific semantics.
For example, the IR for machine learning is modeled as computation graphs, while the IR for LLVM is modeled as a sequence of program instructions.

Take the Circuit IR Compilers and Tools (CIRCT) [2] project as an example. It leverages the MLIR framework to build a compiler for heterogeneous compilation by defining 26 new dialects with 145 new operations. For example, CIRCT uses a generic hardware abstraction by defining the  and  custom dialects with operations to represent abstract hardware modules and combinational logic.
Listing <ref> shows a snippet of MLIR representing a hardware module containg a custom MLIR operation called  which represents combinational addition.

The fast evolution of the underlying IR presents challenges for developing custom test generators. Google reported in 2020 that over 60 dialects have been defined internally in MLIR [3].
In the four years since the MLIR project's initial public release, 29 downstream projects like CIRCT have each contributed one or more custom dialects [2, 4].
General-purpose fuzzers such as AFL++ [5] fail to effectively generate or mutate MLIR due to its highly structured form.
For instance, syntactically correct MLIR must have proper nesting of operations, the correct number of operands and outputs for each operation, valid type annotations, and valid attribute names and values.
Grammar-based fuzzers, such as Grammarinator, use a context-free grammar to constrain input generation, but such grammars cannot encode context-specific constraints [6].
Custom generator-based fuzzers in the vein of CSmith [7], NNSmith [8], and MLIRSmith [9] manually encode constraints in terms of imperative code.
Such constraints require significant effort to write and struggle to adapt to the fast continual introduction of new dialects.

We observe that the fast-evolving compiler infrastructure of IRs
requires a test input generator that can encode or learn constraints automatically. To this end, we propose a new approach called , drawing inspiration from techniques for automated patch synthesis [10, 11, 12].
These techniques synthesize code edits from examples,
learning the code contexts in which the transformations are appropriate and concretizing the code edits to the matching code contexts.

Like generator-based fuzzers,  is capable of preserving context-sensitive constraints such as
the cardinality of operation arguments and return values, the def-use relationships of values, and the consistency of type annotations.
The key novelty is that  can do so
without the significant manual effort required to write custom generators by hand.
accomplishes this by synthesizing parameterized mutations from seed test cases.

caption=This MLIR code snippet uses a new hardware  dialect comb for combinational logic in the CIRCT project.,

Colored pairs in Listing <ref> represent the def-use relationships and type consistency that needs to be satisfied.
A parameterized mutation derived from Listing <ref> would encode the knowledge that the operation  is nested within the  denoted as ancestor $k_1$, is preceded by one  operation denoted as $l_1$, and followed by one  operation denoted as $r_1$. This knowledge enables  to select an appropriate context to apply the mutation by matching the $k$-ancestors and $l$-siblings (and $r$-siblings) of the  operation.
The parameterized mutation also encodes the knowledge that  takes two arguments  and , and returns one value  all of which have the same type .
parameterizes these arguments and types and then re-concretizes them based on the target context to which the mutation is applied.

We compare the effectiveness of  against Grammarinator, MLIRSmith, and NeuRI.
Grammarinator was chosen as a representative grammar-based fuzzer.
MLIRsmith was chosen as a representative generator-based fuzzer.
NeuRI was chosen as a custom test generator with limited parameterization—i.e. it parameterizes the tensor shapes and operation numerical attributes.
We evaluate  on four MLIR-based compiler projects: LLVM, ONNX-MLIR, Triton, and CIRCT.
These are chosen as representative MLIR projects that define 42, 2, 4, and 26 custom dialects respectively.
For all dialects except the 13 targeted by MLIRSmith and the 1  dialect that can be targetted by NeuRI, no custom test generators exist.
Writing test generators for these custom dialects is time-consuming.
As an example, MLIRSmith's implementation totals  lines of code with  lines of code per dialect on average [13].

We assess 's fault detection potential by measuring code coverage and input diversity.
We measure input diversity in terms of MLIR dialect pair coverage.
Dialect pair coverage [9] is defined as the number of unique pairs of operations/dialects that have a data dependency or control dependency.
Averaged across over four MLIR compiler projects,  outperforms Grammarinator, MLIRSmith and NeuRI in terms of branch coverage by ,  and  respectively.
In terms of dialect pair coverage,  outperforms Grammarinator, MLIRSmith and NeuRI on average by , , and .
Compared to MLIRSmith and NeuRI,  is capable of covering 60 new custom dialects defined by the four MLIR projects.
discovers a previously undiscovered bug in CIRCT.

In summary, this paper makes the following contributions:

* We design a novel compiler fuzzing technique that obviates the need for defining custom mutations apriori, which is impractical when the target IR is highly extensible and constantly evolving.

* Our method automatically synthesizes and applies multi-edit, dependence-aware, custom mutations on the fly. The key enabler is the construction of parameterized mutations from test examples, and the concretization of the mutations after establishing the context through ancestor path or prefix(postfix) matching.

* We show that our method achieves  greater code coverage and  greater dialect coverage within the same time budget compared to existing baseline fuzzers.

The remainder of this paper is organized as follows.
Section <ref> introduces MLIR and a motivating example.
Section <ref>  presents the design and implementation of .
Section <ref> provides the design of our experiments and their results.
Section <ref> discusses
possible threats to validity.
Section <ref> presents related work.
Finally, we draw the conclusions of our work in Section <ref>.

§ BACKGROUND

§.§ MLIR: Multi-Level Intermediate Representation

Multi-Level Intermediate Representation (MLIR) is a modular compiler framework that differs from traditional approaches by enabling developers to extend the intermediate representation.
Rather than defining a single monolithic IR with a fixed set of types and instructions like LLVM's IR, MLIR is extensible by design.
Compiler developers may define new MLIR dialects consisting of custom operations and types tailored to the domain, language, or architecture the compiler targets. MLIR dialects can be progressively lowered, forming a modular compilation pipeline, in contrast with traditional compiler infrastructure that offers limited extensibility.
However, this presents a challenge for test generation, since custom operations introduce semantic constraints that are operation-specific, such as the def-use relationships and type consistency illustrated by colored pairs in
Listing <ref>.

Take the Circuit IR Compilers and Tools (CIRCT) [2] as an example.
CIRCT is a unified framework built on MLIR that enables optimized hardware design across different backends catering to the needs of heterogeneous compilation.
It defines 26 new dialects with 145 new operations, including the  and
dialects that define low-level hardware operations. An example of the  add operation is shown on line 4 of Listing <ref>.
The full name of this operation is  where  is a dialect name and  is the operation name.
As shown in the snippet, the operation takes two operands  and returns a single value . Its type signature indicates that the operation takes an input operands of type  (2-bit integers) and produce an output of type .

§.§ Motivating Example

caption=A donor program $P_d$ from which a mutation for inserting the  operation is synthesized from.

caption=A recipient program $P_r$ to which the mutation for inserting the  operation from Listing 2 should be applied to.

caption=A test case created by Grammarinator[6]'s recombine operation. It deletes line4 and adds PastelGreenline 5. This test case is invalid as it violates the PastelDarkdef-use relation and the PastelDark2type consistency.

caption=A test case created by 's context-dependent, parameterized mutation. This mutation replaces an operation  with PastelGreen. The test case is valid as  matched a corresponding context before PastelBlueconcretizing its mutation to the target context. ,

Existing mutation strategies such as recombining test fragments frequently fail to generate test cases capable of exercising deeper compiler logic.
This failure is caused by the large proportion of invalid test cases generated, which violate early checks made by the compiler.
For example, a) the definition of identifiers needs to exist before they are used (def-use), b) the types of variables need to remain consistent through the test case (type consistency), and c) the number and type of arguments that match what is required by an operation (signature consistency).
To address the limitation of existing fuzzers,
we present an approach that synthesizes parameterized mutations, aiming to implicitly capture these constraints.

Consider the following seed test cases: a “donor” program $P_d$ in Listing <ref> that contains the  operation to be inserted in the “recipient” program $P_r$ in Listing <ref>.
We demonstrate how grammar-based generation and recombination are unlikely to produce a valid program shown in Listing <ref>.

A grammar-based mutator following a general MLIR grammar is unlikely to produce Listing <ref> because the grammar does not include operation semantics defined by MLIR dialects.
For any given operation, the generic MLIR grammar only specifies that the syntax of an operation must have a name (e.g. ), 0 or more return values, arguments and attributes, and a type signature.
Therefore, a grammar-based fuzzer generating a  operation would be unaware of the signature of the operation as defined by the  dialect.
Specifically, without a grammar for the dialect, the fuzzer would be unaware of the associations between variables and their types, e.g. ,  has the type , and operation-specific signature such as  having exactly two input values and one return value.

Another common grammar-based mutation strategy is to recombine the fragments of existing tests with other test cases.
To illustrate,  at line 4 of the recipient program $P_r$ in Listing <ref> is replaced with  from line 4 of the donor program $P_d$ in Listing <ref>, producing the mutated test in Listing <ref>.
However, after the replacement, the values and types of the  operation are inconsistent with its new surrounding context.
The resulting test will be rejected early by the compiler as it violates the def-use constraint, since the value  was not defined before it was used.
Inferring such semantic constraints (often Turing-complete) is challenging as discussed in previous works [14] [15] [16].

Listing <ref> highlights the changes required to adapt the code using  from program $P_d$ to the context of program $P_r$.
To satisfy the def-use constraint,
the values referenced as arguments to an operation (e.g.  on line 5) must be previously defined (e.g.  on line 3).
To satisfy type consistency,
the initially assigned types, such as , for  on line 3 must remain consistent in its subsequent references, such as its use as an argument and the resulting return type on line 5.

To generate test cases that satisfy these constraints, one can write custom generators or refine new grammars to encode these constraints.
However, this requires hand-coding the constraints of each operation defined in a dialect, and the cost is exacerbated for rapidly evolving projects—those that use MLIR—because the specialized grammar or custom generators will need to be updated as new dialect operations are added, modified, or removed.

In this paper, we propose to automatically synthesize custom mutators.
Existing test cases of MLIR dialects demonstrate how the dialect-specific operations should be invoked. Our key insight is that these test cases implicitly encode the various constraints of MLIR dialects, e.g., def-use, operations' type signature, and therefore, matching the code context would lead to a higher chance of successfully generating valid test cases.
For example, the donor test case in Listing <ref> and the recipient test case in Listing <ref> exhibit a structural similarity.
is able to identify such similarity and synthesize a parameterized mutation that captures the context of the operation  in the donor test case. Applying the mutation,  produces a valid test case as shown in Listing <ref>, which respects the dialect-specific constraints, and hence is able to exercise deeper logic in the MLIR compiler.

§ APPROACH

Figure <ref>
describes 's fuzzing loop.
Each iteration synthesizes a custom mutation from a donor test case and transplants it onto a recipient test case.
In the $\synth$ step
(Section <ref>),
selects a donor test case and a recipient test case.
From the donor test case,  infers a parameterized mutation with a parameterized context.
In the $\synthlocate$ step (Section <ref>),
as the mutations are context-dependent,
matches the parametrerized context against the recipient test case to identify a suitable location for the mutation.
The $\synthmatch$ step (Section <ref>) then creates a variable binding of parameters to concrete program fragments from the matching context.
Finally, $\instantiate$ (Section <ref>) concretizes the mutation and transplants it into the recipient test case.

§.§ $\synth$: Synthesizing a parameterized mutation.

Parameterized mutations are synthesized from seed test case which we will refer to as donor test cases.
Given a donor test case like Listing <ref>,  parses the test case using a generic MLIR grammar to produce a donor parse tree.
From the donor parse tree,  constructs custom mutator comprising of an parameterized mutation and a parameterized context as shown in Figure <ref>.

A flowchart of 's fuzzing loop

The parameterized mutation is a parameterized partial parse-tree that contains the content to be inserted by  when mutating a test case.
The parameterized context is similarly a partial parse tree that captures the conditions in which parameterized mutation may be instantiated.

$\synth$ uniformly randomly selects a sub-tree in the donor's parse tree as the parameterized mutation to be transplanted.
The parameterized context and parameterized mutation are extracted by bisecting the donor parse tree along at the selected sub-tree's root node as shown in Figure <ref>.
The parameterized context encodes information such as the operations before and after the parameterized mutation, their ordering, the nesting of operations, and the potential locations of parameters.
For example, as shown in Figure <ref>, the parameterized context encodes the information that  is preceded by a block label  and the operation , and succeeded by a  operation.
It also encodes the nesting information that , , , and  are nested within .

[label=lst:synth-example, caption=In this donor test case $P_d$, the boxed area represents the source of a grafted, parameterized mutation. The rest unboxed area represents the potential source of a corresponding, parametrized context.]
"hw.module"() (
^bb0(|hr%arg0|: |hbi2|):
|hp%c1| = "hw.constant"() value = -2 : i2 : () -> |hbi2|
|hg%o1 = "comb.add"(hr%arg0, hp%c1) : (hbi2, i2) -> hbi2|
"hw.output"(|hg%o1|) : (|hbi2|) -> ()

This diagram illustrates how $\synth$ decomposes the donor test case $P_d$ shown in Listing <ref> into a parameterized context and parameterized mutation. For example, concrete symbols such , , , and  are now paramterized as placeholders such as hrA, hpB, hbC, and hgD respectively.

Since the donor's mutation may contain identifiers and types that are not defined in recipient programs, a naive transplantation will likely produce an invalid input that violates def-use and type consistency constraints.
$\synth$ uses a heuristic that common sub-strings in the input can be indicators of context-dependent constraints such as def-use and type consistency.
$\synth$ parameterizes the context and mutation by introducing a parameter for each common sub-string between the context and the mutation.
In Figure <ref> $\synth$ creates 4 parameters: A, B, C, and D with an initial binding of
, , , and
as illustrated with matching colors in Figure <ref>.
Later, each parameter can be concretized with a suitable sub-string from the context of the recipient.

§.§ $\synthlocate$: Selecting mutation location depending on the target context

looks for locations where the parametrerized context matches the recipient input to increase the likelihood of satisfying the constraints.
Three factors are considered: the number of matching ancestor nodes $k$, left-sibling nodes $l$, and right-sibling nodes $r$.
Matching $k$ ancestors with the parameterized context ensures that the mutation is made in a similar level of nesting.
This prevents situations such as improperly nested functions, or operations being inserted outside of functions.
Matching $l$ left-siblings and $r$ right-siblings with the parameterized context ensures that if an mutation pattern is of an operation, then the operation will likely be inserted in a location where the required number of operand values (left) is available, and the results of the parameterized mutation will be used accordingly (right).

$\synthlocate$: Finding a valid mutate location by matching $k$-ancestors and $l$($r$) siblings.
[1]

* $context \gets$ the parametrized context

* $recipient \gets$ the recipient parse tree

* $mutateLocation \gets$ a parse-tree node in the recipient test case that represents a valid mutate location

$candidate \gets \text{walk}(recipient)$
$isMatch \gets$ true
The following loop jointly assigns $\getNext$ and $m$
$(\getNext, m) \in \{\hspace{0.5em}(\getParent,k)$,

$pNode \gets context$
$cNode \gets candidate$
$i \in [0, m)$
$\pName(pNode) \neq \pName(cNode)$
$isMatch$ $\gets$ false
$pNode \gets \getNext(pNode)$
$cNode \gets \getNext(cNode)$
yield candidate

Algorithm <ref> describes how the mutate location is selected.
The values $k$, $l$, and $r$ are global hyper-parameters that are set by the user. In our evaluation, we set $k,l,r=4$.

On line 1, the $\text{walk}$ function returns each node of the recipient parse tree in breadth-first order. Each node considered a candidate mutate location.

On line 4 of the algorithm, $\getNext$ and $m$ are jointly assigned so that when $\getNext \gets \getParent$ then $m \gets k$ and when $\getNext \gets \getLeftSibling$ then $m \gets l$.
The $\getParent(n)$, $\getLeftSibling(n)$, and $\getRightSibling(n)$ functions on line 3 take a parse tree node $n$ and return the parent node of $n$, the node that precedes $n$ at the same depth, or the node that succeeds $n$ at the same depth respectively.
In Listing <ref> calling $\getParent$, $\getLeftSibling$, and $\getRightSibling$ on  returns the enclosing block node (representing lines 2-7), the prior operation node (representing line 2), and the next operation node (representing line 5) respectively.

On line 11 of the algorithm, the $\pName(n)$ function returns the name of the production rule that corresponds with the parse-tree node $n$.
For example, calling $\pName$ on the  operation of Listing <ref> returns the rule name "operation".

Listings <ref> and Figure <ref> show an example of the $k$-ancestor, $l$-sibling, and $r$-sibling matching process.
$\synthlocate$ compares the parameterized context to each candidate location in the recipient test case.
Location A is a valid location since it has an operation as a left and right sibling (lines 3 and 5 respectively), and is nested within a block (line 2) and within a operation (line 1).
Location B is invalid because it is at the end of the block and thus has no right-siblings.
Location C is invalid because it has no right-siblings and its ancestor node is an operation, whereas the parameterized context requires the first ancestor to be a block.

Apart from replacing existing parse-tree nodes,  is also able to transplant content by inserting them in locations corresponding to quantifiers in production rules of the grammar.
Such quantifiers indicate that a varying length collection of terms can be generated.
locates parse-tree nodes that correspond to production rule and inserts a new node corresponding to the quantified term.
can then apply the same $k$-ancestor, $l(r)$-sibling matching logic described earlier to decide if the newly inserted node is a suitable mutation location.
This grants  greater flexibility, increasing the diversity of inputs generated.

caption=A set of potential insertion locations are marked as A, B, and C in the recipient test case.,

Illustration of $k$-ancestor and $l(r)$-sibling context matching. Location B is invalid due to not matching the postfix context with $r=1$. Location C is invalid due to not matching the $k$-ancestor path context as the parent node is an operation, not a block with $k=2$.

§.§ $\synthmatch$: Matching and extracting parameters

An illustration of the $\synthmatch$ step. When the recipient test case in Listing <ref> is matched with the parameterized context shown in this figure, the parameters hrA, hpB, hbC, and hgD are bound to the concrete values , , , and  respectively.

Once an mutate location is selected in the $\synthlocate$ step, $\synthmatch$ performs a joint breadth-first traversal of the parameterized context tree and the parse-tree of the recipient test case to compute parameter assignments.
The traversal starts at the mutate location of the recipient tree and the root of the parameterized mutation within the parameterized context.
An annotated example of this traversal is illustrated in Figure <ref>.
A node pair is considered a match if the parse tree node name is the same between the parametrerized context and recipient parse tree.
This allows parse tree nodes of different concrete operations to match.
For example, node pair 2.2 in Figure <ref> is considered a match even though the operation names ( and ), types ( and ), and values ( and ) differ.

When a parameter node is encountered during the traversal of the parametrerized context,  assigns it to the corresponding sub-tree in the traversal of the parse tree of the recipient input.
In Figure <ref>, the parameters A, B, C, and D from the parametrerized context are assigned to the matching nodes for , , , and  in the recipient parse tree.
When there are duplicate assignments as in parameter C, $\synthmatch$ will uniformly randomly select one of the assignments to use.

§.§ $\instantiate$: Concretize the mutation

[label=lst:match-example, caption=The recipient test case where the parametrerized mutation is inserted and concretized. The parametrerized mutation is boxed on line 4. By instantiating the pattern in this new context, the following substitutions are made: hrA$\gets$, hpB$\gets$, hbC$\gets$, and hgD$\gets$.
"hw.module"() (
^bb0(|hr%arg0: hbi4|, |hp%0 = "hw.bitcast"(%arg1) : (!hw.array<2xi2>) -> hbi4|
|hg%1 = "comb.add"(hr%arg0, hp%0) : (hbi4, i4) -> hbi4|
|"hw.output"(hg%1) : (hbi4) -> ()|

In the $\instantiate$ step,  adapts the parameterized mutation to the recipient test case by substituting in the parameter assignments extracted during the $\synthmatch$ step.

Listing <ref> shows how the parametrerized mutation is instantiated.
Here, parameters A, B, C, and D corresponding the return value, two operands, and the types are assigned the values
, , , and  respectively.

also checks that the mutated input conforms to generic MLIR constraints before passing them to the compiler.
For example, a mutation may lead to test cases that redefine the same variable twice or use an undefined variable.
Such test cases are invalid in any MLIR program, regardless of dialect.

§ EVALUATION

In our study, we examine the following research questions:

*  How effective is  in terms of increasing code coverage?

*  What is the diversity of test cases generated by  in terms of dialect pair coverage?

*  Does context-based positioning of mutation locations improve the likelihood of a valid mutation?

*  Does parameterization of the mutation content improve the likelihood of a valid mutation?

Branch coverage for each subject program.   outperforms a grammar-based fuzzer by up to 1.51$\times$ and improves coverage by up to 1.47$\times$ compared to existing seed tests.

§.§ Experiment Design

Benchmark programs

Subject Program     Description      # of Seed      # of Dialects

mlir-opt (P1)     Includes the core and contributed MLIR dialects part of the LLVM project.     1,692     42

onnx-mlir-opt (P2)     An MLIR-based ONNX compiler.     1,885     2

triton-opt (P3)     An MLIR-based compiler for the Triton language.     29     4

circt-opt (P4)     An MLIR-based compiler for electronic design automation (EDA).     377     26

It is costly to hand-write custom test generators for MLIR-opt and CIRCT projects due to the large number of MLIR dialects they define. MLIRSmith  supports only 13 dialects currently.

In our evaluation of , we select four active projects that use the MLIR compiler infrastructure, shown in Table <ref>.
Each project provides a utility executable named  which is used to independently invoke and test one or more compiler passes.
To fuzz each project, we invoke the  executable with a pipeline of $P$ randomly selected compiler passes on each test case generated by a fuzzer.
In practice, we set $P=5$ since most unit test cases written by developers only invoke one to three compiler passes at a time.

For ONNX-MLIR, LLVM, and CIRCT, we select compiler passes based on the dialects present, identified by the operator names in the test case.
For example, if a test case contains the  operation, then our test driver will select a compiler pass that operates on the  dialect such as the  pass which lowers certain  operations to the  dialect.
As Triton's compiler passes do not follow this naming scheme and this heuristic cannot be used, we select compiler passes randomly from all available passes.

§.§.§ Locating Seed Test Cases

We build a corpus of seed test cases for each subject program by locating and splitting ".mlir" files in each subject program's respective project repositories for a total of 1,692, 1,885, 26, and 377 seed test cases respectively.
Then we convert each test case into its generic MLIR syntax form to remove syntactic sugar and enable it to be parsed using a single generic MLIR grammar for all subject programs.

§.§.§ Evaluation Measures

To evaluate and compare the fault detection potential of , we use the following measures:

* Branch coverage is computed as the number of covered branches as reported by LLVM's SanitizerCoverage code coverage instrumentation.

* Dialect coverage is a measure of the input diversity used in the evaluation of prior work, MLIRSmith [9]. This notion can be further divided into control dependent dialect coverage and data dependent dialect coverage. The idea is to use multiple dialects in tandem, and to ensure that distinct dialects are used together in a meaningful manner by being connected through data or control dependencies.

* Control dialect coverage is computed by counting the number of unique dialect pairs whose operations are linked by a control dependency.
For example, Listing <ref> contains two control dependent dialect pairs, (, ) and (), since  (line 2) and  (line 3) are nested within  (line 1) forming a control dependence.

* Data dialect coverage is computed by counting the number of unique dialect pairs whose operations are linked by a data dependency.
For example, Listing <ref> contains one data dependent dialect pair,
(, ) since
(line 3) takes the output  of  (line 2), thus forming a data dependence.

[label=lst:control-dep-ex, caption=In this example,  (line 3) and  (line 4) have a control dependence on  (line 2), forming two dependent dialect pairs (, ) and ().  (line 4) also has a data dependence on  (line 3) forming a data dependent dialect pair (, ).]
|"sv.if"|(|%18| = |"hw.constant"|() value = 10 : i32 : () -> i32
,  // ...

§.§.§ Baselines

We evaluate  against Grammarinator [6], MLIRSmith [9], and NeuRI [17].
Grammarinator represents a baseline grammar-based fuzzer, while MLIRSmith and NeuRI represent the state of the art custom generators for MLIR and deep learning models.

Grammarinator converts ANTLR4 grammar definitions into generation models that can be used to generate, mutate, and recombine test cases following the grammar.
In our experiments, we provide both  and Grammarinator with the same seed corpus for a fair comparison.

MLIRSmith is a custom generator-based fuzzer that targets MLIR's core dialects.
MLIRSmith was chosen for comparison as it specializes in generating valid random MLIR programs, but requires users to implement custom generators for each new dialect. As of March 2024, MLIRSmith supports 13 out of 42 available core dialects [13].
NeuRI is a DL model-level fuzzer that generates computation graphs based on DL-model specific, API-level constraints.
NeuRI supports parameterization only in the form of tensor shape constraints and shape propagation rules for machine learning models.
While NeuRI does not directly target MLIR, the  tool can be used to lower the models generated by NeuRI to the core MLIR dialects for P1 (mlir-opt) or to the  dialect for P2 (onnx-mlir-opt).

We also compare  against running existing test cases (i.e., the seeds for  and Grammarinator). By measuring the branch and dialect coverage of the seed test cases alone, we separate the contributions of the increased coverage afforded by the fuzzers' mutation capability from the innate capability of the seed corpus they draw from.

§.§.§ Experimental Environment

All experiments are performed on an AMD Ryzen 2950X 16-Core Processor with 32 GB of RAM running on Ubuntu 22.04.

Dialect coverage for each subject program.

Subject     3r|P1 (mlir-opt)     3r|P2 (onnx-mlir-opt)     3r|P3 (triton-opt)     3rP4 (circt-opt)

dialects     control     data      dialects     control      data       dialects     control      data       dialects     control      data

SynthFuzz     27     129     100     9     23     24     7     15     4     20     86     40

Seed tests as is    28     68     56     9     17     11     7     12     4     23     57     40

Grammarinator     27     63     49     8     15     8     7     12     4     17     43     27

MLIRSmith     13     62     65     4     6     3     3     3     1     6     15     10

NeuRI     7     17     12     6     9     10     3     3     2     6     14     10

Seed test cases refers to each subject's respective test suite.  achieves greater dialect coverage compared to baseline fuzzers.

§.§ <ref> Branch Coverage

Figure <ref> shows the branch coverage of  and the baseline fuzzers on the four subject programs.
Averaging across all subject programs,  outperforms Grammarinator, MLIRSmith, and NeurRI by , , respectively.

On P1 (mlir-opt)  outperforms Grammarinator, MLIRSmith, and NeuRI by , , and  respectively.
On P4 (mlir-opt)  outperforms Grammarinator, MLIRSmith, and NeuRI by , , and  respectively.

On P2 (onnx-mlir-opt),  is similar to  NeuRI, with less than 1% difference in coverage.  This demonstrates that  can match the performance of a domain-specific fuzzer, NeuRI, by bootstrapping parameterized mutations from existing test cases without hand-coding any custom generator logic. NeuRI implements custom test generator logic for ONNX models (computation graphs for DL models).

On P3 (triton-opt), Grammarinator outperforms  in terms of branch coverage by 1.04$\times$.
P3 only provides 36 test cases in its repository that  and Grammarinator could use as seeds.
Since  relies upon seed test cases to synthesize its custom mutations,
the low number of seeds constrained 's ability to generate diverse test cases.

An example bug found.
discovered a new bug in CIRCT (Issue #6799), which has been confirmed and fixed by the developers.
This bug occurs when the  pass is invoked on an  operation with a block without a terminator operation, such as  or .
The CIRCT compiler incorrectly assumes that the  operation always contains a terminator, and crashes due to the violation of this dialect-specific requirement.
The CIRCT verifier should have detected this absence of a terminator and rejected the  operation.

[label=lst:circt-bug, caption=CIRCT crashes on this minimized input due to not checking for a terminator within . Reported on Mar 7, 2024, the bug was fixed immediately , numbers=none]
module llhd.proc @empty() -> ()

demonstrates up to  improvement on branch coverage over most baseline fuzzers without requiring any hand-coding of custom generator logic.

§.§ <ref> Dialect Diversity

Table <ref> summarizes the performance of  as compared to Grammarinator, MLIRSmith and NeuRI in terms of dialect control/data pair coverage (described in Section <ref>).
SynthFuzz outperforms Grammarinator, MLIRSmith and NeuRI by  and  and  in terms of control dependent dialect pairs and , ,  in terms of data dependent dialect pairs.

To validate whether  discovers new dialect pairs not covered by the seed corpus, we also measure the dialect pair coverage of the seed corpus as a baseline.
For each subject and fuzzer combination, we report the number of unique dialects and the number of unique control and data dialect pairs.
Across all subjects,  covers  new control-dependent and  new data-dependent dialect pairs that did not already exist in the seed corpus.

[label=lst:synthfuzz_unique, caption=A test case generated by  that was not generated by any baselines.
inserts the underlined line 5 and substitutes in the operand  and type , satisfying the required def-use and type consistency constraints.
This test case achieves a new dialect pair coverage, (, ) by introducing the  operator.  ]rq1.mlir

Listing <ref> shows an example test case that can be generated by , but cannot be generated by the baselines.
The  dialect is not supported by MLIRSmith. MLIRSmith currently implements test generator logic for 13 dialects only, as it takes  lines of code on average to support each dialect.
Grammarinator's naive recombination fails to satisfy def-use and type consistency constraints by inserting line 5 as , which references an undefined variable  and uses an incorrect type  for variable . This is because Grammarinator's recombination is context-unaware and is not concretized to fit the target insertion context.

While Grammarinator takes the same set of seed tests as , it achieves  lower dialect diversity than  or the seed tests alone, because Grammarinator alternates between generation, mutation, and recombination modes. Approximately, one third of its time is spent on the pure generation mode that does not use seed test cases.

achieves greater dialect  diversity, compared to
other baseline fuzzers: average  improvement in terms of control-dependent dialect pairs and average  in data-dependent dialect pairs.

§.§ <ref> Context-based Positioning of  Mutation

selects an appropriate insertion location to inject a parameterized mutation by matching the mutation's parameterized context against the target context of the recipient test case. To test the individual effect of the context matching requirement for a parameterized mutation, we vary $k$ from 0, 2, and 4 when matching a $k$-ancestor path. Similarly, we vary $l$ from 0, 2 and 4, when matching a $l$-sibling prefix $l$, and we vary $r$ from 0, 2, and 4 when matching a $r$-sibling postfix. Each trial consists of 10,000 test cases generated by  for P1 (mlir-opt).

As shown in Table <ref>, setting each parameter $k$, $l$, and $r$ to 4 improves the number of valid test cases by , , and  respectively. This indicates that using more context information increases the chance of finding an appropriate location for injecting a grafted mutation, thus increasing the portion of valid test cases. A test case is considered valid, if feeding the generated input to the target program returns zero, indicating a success.

Setting $k=4$ decreases dialect pair coverage by 10%. This may indicate that a very restrictive requirement for matching context by increasing $k$ can negatively affect the input diversity of generated tests. Additional experiments with k greater than 4 had minimal effect on the number of valid tests, as most seed tests have an operation nesting depth less than 4.

Average branch coverage, dialect pair coverage, and valid test cases.

Parameter     Branch Cov.     Dialect Pair Cov.     Valid Test Cases

$k=0$     24,764     100     677

$k=2$     24,765     100     698

$k=4$     24,987     90      749

$l=0$     25,055     94      684

$l=2$     24,749     97      710

$l=4$     24,713     98      729

$r=0$     24,657     97      706

$r=2$     24,901     95      687

$r=4$     24,958     98      731

Increasing $k$, $l$, and $r$ to 4 increases the number of valid test cases by 1.11$\times$, 1.07$\times$, and 1.03$\times$

Increasing ancestor-path, prefix, and postfix requirements for context positioning improves the proportion of valid test cases.

§.§ <ref> Effect of Parameterization

has capability to parameterize and concretize a variable name, an argument's type, and an operation's attribute (e.g.  has a value attribute  with the type ) to fit the target context where a grafted mutation is inserted into.
The goal of parameterization is to preserve context-sensitive constraints such as the def-use constraint (i.e., a value must be defined before use) and the type-constraint (i.e., the type annotation of a value must be consistent throughout its scope).

Validity of test cases generated by .

Violation Type          W/ Param.     W/O Param.

[t]6*Invalid     [t]2*Dialect Specific     Count     4,259     2,450

Percent     38.1%     23.7%

[t]2*General MLIR     Count     1,777     3,120

Percent     15.9%     30.2%

[t]2*Invalid Options     Count     4,356     4,052

Percent     39.0%     39.2%

[t]2*Valid     [t]2*Valid     Count     772     702

Percent     6.9%     6.8%

Parameterization reduces General MLIR violations from 30.2% to 15.9%.

We create a downgraded version of  by turning off its parameterization and concretization capability denoted as W/O Param in Table <ref>.
We generate 10,000 test cases with each version and categorize the test cases based on the error message returned by the target program.

Parameterization increases the proportion of valid test cases by 0.01% only.
However, when we further inspect the underlying reasons for invalid test cases, we find that  increases the chance of adhering to the general MLIR constraints.

With parameterization, 772 tests are valid with the return value zero indicating success, when the tests are fed to the target program. We then categorize the remaining 9228 invalid test cases into three categories based on the type of violation reported by the target program.

* Dialect Specific: 4,259 test cases generated with parameterization are rejected by the target program with a dialect-specific error message such as:  op result #0 must be tensor of 1-bit signless integer values,  op requires a single operand, etc.

* General MLIR: 1,777 test cases generated with parameterization are rejected by the target program with a general MLIR error message such as: an undefined symbol, use of undeclared SSA, redefinition of SSA value, etc.

* Invalid Options: 4,356 test cases generated with parameterization are rejected with an error message, “no such option exists.” This occurs due to the test driver's random pass selection which may pair an option with a pass that does not accept said option.

With parameterization enabled,  generates 1,343 fewer test cases that violate general MLIR constraints out of 10,000 tests.
The proportion of Invalid Options category is approximately the same with and without parameterization. However, the proportion of General MLIR invalidity increases from 15.9% to 30.2% when disabling parameterization.
This is due to the fact that without parameterization, the content of parameterized mutation is not concretized to fit the recipient context. Thus it is more likely to violate general MLIR constraints such as def-use and type consistency.

Listing <ref> shows an example of a test case generated by  which nests the  operation within a  operation.
parameterizes  the input arguments and their types, thus passing the general MLIR constraints such as def-use and type consistency.

reduces the proportion of general MLIR constraint violating tests from 30.2% to 15.9% by parameterizing the injected mutation's content.

§ THREATS TO VALIDITY

§.§.§ Limited Fuzzing Time
In our experiments on code and dialect coverage, we limit the fuzzing budget to 4 hours for each fuzzer.
While unlikely, continuing the fuzzing campaign for longer may reveal different trends than our evaluation showed.

§.§.§ Choice of Subject Programs
The results of our evaluation is influenced by our choice of subject programs. To minimize bias, we selected four MLIR projects to represent a wide variety domains among 40 possible public MLIR projects. P1 (the LLVM/MLIR project) was chosen as it contains the original core MLIR dialects that MLIRSmith defines its custom generators for.
P2 is a deep-learning compiler for ONNX models that NeuRI can directly fuzz. P3 is a compiler for the Triton language. P4 (CIRCT) is a novel application of MLIR to the domain of hardware design and synthesis.

§ RELATED WORK

Grammar-based fuzzing. Grammar-based fuzzers, e.g. Grammarinator [6], Nautilus [14], LangFuzz [18], are guided by a grammar. PolyGlot  [19] transforms the high-level languages into a general IR with the BNF grammar given by the users and uses constraint mutators to preserve the grammar.
Our experiments found that 97% of Grammarinator's generated inputs fail to satisfy semantic constraints, e.g., type consistency, or more complex relationships over shapes and types.
, instead, automatically encodes these semantic constraints from examples.

Custom generator- and mutation-based fuzzers.
Generator-based fuzzers [20, 21] require generators, written by human developers in an imperative language, to produce valid inputs.
CSmith [7] generates random C programs for fuzzing C compilers.
Related to our target subject of MLIR, MLIRSmith [9] generates random MLIR programs.
Unlike grammar-based fuzzers, they can encode constraints that are difficult to express in grammar.
Despite the additional human effort required, MLIRSmith underperforms  as it is unable to satisfy the constraints of invoking each operator of a new dialect.
does not require the definition of domain-specific custom mutators to successfully invoke operators from novel dialects.

Several studies have proposed fuzzers targeted at specific domains.
Apart from fuzzing MLIR dialects,
BigFuzz [22] was proposed for Apache Spark programs,
Qdiff [23] for quantum programs,
HeteroFuzz [24] for heterogeneous applications.
GrayC [25] designed custom mutators for fuzzing C programs. NNSmith [8] designed a generator for computation graphs to fuzz deep learning compilers.
To effectively generate inputs, these fuzzers employ custom mutators.
These mutators are hand-crafted and manually implemented for each domain.
The amount of work needed to develop a fuzzer for each domain highlights the need for approaches capable of automatically synthesizing custom mutators.

The approaches above do not allow for mutations that are parameterized.
The closest work to  is NeuRI [17], which infers constraints over tensor shapes to generate deep learning (DL) models for fuzzing DL compilers.
However, because it is specific to DL compilers and limited in the types of constraints inferred, NeuRI did not achieve a high coverage in our experiments.

Learning constraints.
Other techniques check that inputs satisfy constraints during fuzzing.
Dewey et al. [26] uses Constraint Logic Programming  to specify constraints test generation.
ISLA [16] allows semantic constraints to be applied during grammar-based fuzzing.
These techniques require significant human effort, requiring human-written constraints by hand [26] or  templates [16].

Learning code patterns and transformations.
Code pattern inference techniques have been adopted in studies for code search [27], mining rules for detecting bugs [28], and code quality [29].
Other techniques  synthesize patches, or the transformation of one program to a subsequent version of the program.
These techniques [10, 30, 12, 31, 11, 32, 33] learn to transform programs from examples.
They identify parameterized patches given examples of the transformation, using the observation that code elements reoccurring across multiple patches are usually essential.
draws inspiration from these techniques by learning  parameterized mutations from examples.
While these techniques aim to mutate a buggy program into a single, correct program,  aims to generate a diversity of mutants for fuzzing.

§ CONCLUSION

We present , a novel approach to compiler fuzzing that address the challenges in testing extensible compilers.
is able to synthesize custom mutations for new MLIR dialects.
In contrast, domain-specific fuzzers require months of development, which is impractical given the rapid evolution of target languages and representations.
synthesizes custom parameterized, context-dependent mutations from the test cases  of each dialect compiler,
exploiting the observation that the dialect-specific constraints  are implicitly encoded in these tests.
can cover 60 dialects that cannot be covered by existing fuzzers, and outperforms existing grammar-based and domain-specific fuzzers in terms of branch coverage by  and dialect coverage by .

A replication package has been made available at <https://figshare.com/s/b96ea4a64f6c6a0ece12>.

[1]
A. F. Brown and G. Wilson, “The architecture of open source applications,” 2011. [Online]. Available: <https://api.semanticscholar.org/CorpusID:14285235>

[2]
“CIRCT: Circuit IR Compilers and Tools,” <https://circt.llvm.org/>, 2023, accessed: 2023-03-11.

[3]
M. Amini, R. Riddle, and Google, “MLIR: Multi-level intermediate representation,” <https://llvm.org/devmtg/2020-09/slides/MLIR_Tutorial.pdf>, 2020, [Accessed 2024-03-15].

[4]
<https://mlir.llvm.org/users/>, 2022.

[5]
A. Fioraldi, D. Maier, H. Eißfeldt, and M. Heuse, “AFL++: Combining incremental steps of fuzzing research,” in 14th USENIX Workshop on Offensive Technologies (WOOT 20).1em plus 0.5em minus 0.4emUSENIX Association, Aug. 2020.

[6]
R. Hodován, A. Kiss, and T. Gyimóthy, “Grammarinator: A grammar-based open source fuzzer,” in Proceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation, ser. A-TEST 2018.1em plus 0.5em minus 0.4emNew York, NY, USA: Association for Computing Machinery, 2018, p. 45–48. [Online]. Available: <https://doi.org/10.1145/3278186.3278193>

[7]
X. Yang, Y. Chen, E. Eide, and J. Regehr, “Finding and understanding bugs in c compilers,” SIGPLAN Not., vol. 46, no. 6, p. 283–294, jun 2011. [Online]. Available: <https://doi.org/10.1145/1993316.1993532>

[8]
J. Liu, J. Lin, F. Ruffy, C. Tan, J. Li, A. Panda, and L. Zhang, “Nnsmith: Generating diverse and valid test cases for deep learning compilers,” in Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2, ser. ASPLOS 2023.1em plus 0.5em minus 0.4emNew York, NY, USA: Association for Computing Machinery, 2023, p. 530–543. [Online]. Available: <https://doi.org/10.1145/3575693.3575707>

[9]
H. Wang, J. Chen, C. Xie, S. Liu, Z. Wang, Q. Shen, and Y. Zhao, “Mlirsmith: Random program generation for fuzzing mlir compiler infrastructure,” in 2023 38th IEEE/ACM International Conference on Automated Software Engineering (ASE).1em plus 0.5em minus 0.4emLos Alamitos, CA, USA: IEEE Computer Society, sep 2023, pp. 1555–1566. [Online]. Available: <https://doi.ieeecomputersociety.org/10.1109/ASE56229.2023.00120>

[10]
N. Meng, M. Kim, and K. S. McKinley, “LASE: locating and applying systematic edits by learning from examples,” in 2013 35th International Conference on Software Engineering (ICSE).1em plus 0.5em minus 0.4emIEEE, 2013, pp. 502–511.

[11]
R. Rolim, G. Soares, L. D'Antoni, O. Polozov, S. Gulwani, R. Gheyi, R. Suzuki, and B. Hartmann, “Learning syntactic program transformations from examples,” in 2017 IEEE/ACM 39th International Conference on Software Engineering (ICSE).1em plus 0.5em minus 0.4emIEEE, 2017, pp. 404–415.

[12]
L. Serrano, V.-A. Nguyen, F. Thung, L. Jiang, D. Lo, J. Lawall, and G. Muller, “SPINFER: Inferring semantic patches for the linux kernel,” in 2020 USENIX Annual Technical Conference (USENIX ATC 20), 2020, pp. 235–248.

[13]
Colloportus0, “GitHub - colloportus0/mlirsmith — github.com,” <https://github.com/Colloportus0/MLIRSmith>, [Accessed 20-03-2024].

[14]
C. Aschermann, T. Frassetto, T. Holz, P. Jauernig, A.-R. Sadeghi, and D. Teuchert, “NAUTILUS: Fishing for deep bugs with grammars,” in NDSS, 2019.

[15]
J. Wang, B. Chen, L. Wei, and Y. Liu, “Superion: Grammar-aware greybox fuzzing,” in 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE), 2019, pp. 724–735.

[16]
D. Steinhöfel and A. Zeller, “Input invariants,” in Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, 2022, pp. 583–594.

[17]
J. Liu, J. Peng, Y. Wang, and L. Zhang, “Neuri: Diversifying dnn generation via inductive rule inference,” in Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ser. ESEC/FSE 2023.1em plus 0.5em minus 0.4emNew York, NY, USA: Association for Computing Machinery, 2023, p. 657–669. [Online]. Available: <https://doi.org/10.1145/3611643.3616337>

[18]
C. Holler, K. Herzig, and A. Zeller, “Fuzzing with code fragments,” in 21st USENIX Security Symposium (USENIX Security 12), 2012, pp. 445–458.

[19]
Y. Chen, R. Zhong, H. Hu, H. Zhang, Y. Yang, D. Wu, and W. Lee, “One engine to fuzz ’em all: Generic language processor testing with semantic validation,” in 2021 IEEE Symposium on Security and Privacy (SP), 2021, pp. 642–658.

[20]
R. Padhye, C. Lemieux, K. Sen, M. Papadakis, and Y. Le Traon, “Semantic fuzzing with zest,” in Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis, 2019, pp. 329–340.

[21]
R. Padhye, C. Lemieux, and K. Sen, “Jqf: Coverage-guided property-based testing in java,” in Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis, 2019, pp. 398–401.

[22]
Q. Zhang, J. Wang, M. A. Gulzar, R. Padhye, and M. Kim, “BigFuzz: Efficient fuzz testing for data analytics using framework abstraction,” in Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering, 2020, pp. 722–733.

[23]
J. Wang, Q. Zhang, G. H. Xu, and M. Kim, “QDiff: Differential testing of quantum software stacks,” in 2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE).1em plus 0.5em minus 0.4emIEEE, 2021, pp. 692–704.

[24]
Q. Zhang, J. Wang, and M. Kim, “HeteroFuzz: Fuzz testing to detect platform dependent divergence for heterogeneous applications,” in Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, 2021, pp. 242–254.

[25]
K. Even-Mendoza, A. Sharma, A. F. Donaldson, and C. Cadar, “Grayc: Greybox fuzzing of compilers and analysers for c,” in Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis, ser. ISSTA 2023.1em plus 0.5em minus 0.4emNew York, NY, USA: Association for Computing Machinery, 2023, p. 1219–1231. [Online]. Available: <https://doi.org/10.1145/3597926.3598130>

[26]
K. Dewey, J. Roesch, and B. Hardekopf, “Language fuzzing using constraint logic programming,” in Proceedings of the 29th ACM/IEEE international conference on Automated software engineering, 2014, pp. 725–730.

[27]
A. Sivaraman, T. Zhang, G. Van den Broeck, and M. Kim, “Active inductive logic programming for code search,” in 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE).1em plus 0.5em minus 0.4emIEEE, 2019, pp. 292–303.

[28]
H. J. Kang and D. Lo, “Active learning of discriminative subgraph patterns for API misuse detection,” IEEE Transactions on Software Engineering, vol. 48, no. 8, pp. 2761–2783, 2021.

[29]
P. Garg and S. H. Sengamedu, “Synthesizing code quality rules from examples,” Proceedings of the ACM on Programming Languages, vol. 6, no. OOPSLA2, pp. 1757–1787, 2022.

[30]
J. Andersen, A. C. Nguyen, D. Lo, J. L. Lawall, and S.-C. Khoo, “Semantic patch inference,” in Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering, 2012, pp. 382–385.

[31]
M. Lamothe, W. Shang, and T.-H. P. Chen, “A3: Assisting android api migrations using code examples,” IEEE Transactions on Software Engineering, vol. 48, no. 2, pp. 417–431, 2020.

[32]
S. A. Haryono, F. Thung, D. Lo, L. Jiang, J. Lawall, H. J. Kang, L. Serrano, and G. Muller, “Androevolve: automated android api update with data flow analysis and variable denormalization,” Empirical Software Engineering, vol. 27, no. 3, p. 73, 2022.

[33]
J. Jiang, L. Ren, Y. Xiong, and L. Zhang, “Inferring program transformations from singular examples via big code,” in 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE).1em plus 0.5em minus 0.4emIEEE, 2019, pp. 255–266.

get arXiv to do 4 passes: Label(s) may have changed. Rerun


# About Code Equivalence - a Geometric Approach

Iliya Bouyukliev and Stefka Bouyuklieva

###### Abstract

The equivalence test is a main part in any classification problem. It helps to
prove bounds for the main parameters of the considered combinatorial
structures and to study their properties. In this paper, we present algorithms
for equivalence of linear codes, based on their relation to multisets of
points in a projective geometry.

##  1 Introduction

The problem for equivalence of linear codes is considered by many authors (see
for example [1, 2, 3]). The most popular and widely used algorithms for code
equivalence are based on the works of J. Leon [4]. His programs are
implemented in the software packages Magma [5] and GAP [6]. Leon’s algorithm
is very good for finding the automorphism group, but doesn’t give a canonical
form. The canonical form is very important for a fast comparison of a large
number of objects and it is the basis of algorithms for generating
combinatorial structures (see McKay [7]).

Our algorithms for equivalence are based on an algorithm for isomorphism of
binary matrices. The set of all binary matrices with $n$ columns can be
partitioned into equivalence classes under the action of the symmetric group
$\mathcal{S}_{n}$. For each class of equivalence we choose one representative
according to a certain rule, which we call a canonical representative. The
canonical form of a matrix is the canonical representative of its equivalence
class. The isomorphism test of matrices is then reduced to comparing their
canonical forms. In addition to the canonical forms, the algorithm used also
calculates the order and generating elements of the automorphism groups of the
considered matrices. For more details on this algorithm, called IsBMiso, see
[1] and [8].

This article discusses the question in which cases the geometric approach in
the linear code equivalence test is more effective, as well as why and how it
can be applied. We compare the developed algorithms with the algorithm
implemented in the program LCequivalence which is a module in the software
package QextNewEdition [8].

The paper is organized in four sections. Section 2 consists of three
subsections in which we give some important information about linear codes,
Galois geometries and the relationship between the codes and multisets of
points in a projective space. We also show an approach how to transform the
problem of code equivalence to the problem of isomorphism of binary matrices.
In Section 3, we describe the algorithms, named CEIMPG (Code Equivalence by
Incidence Matrix of Projective Geometry) and CESIMPG (Code Equivalence by
Shortened Incidence Matrix of Projective Geometry). In Section 4 we present
some experimental results and compare the algorithms CESIMPG and
LCequivalence.

##  2 Preliminaries

Let $\mathbb{F}_{q}$ be a finite field with $q$ elements where $q=p^{m}$ for a
prime $p$. The support $\mbox{\rm supp}(w)$ of a vector
$w\in\mathbb{F}_{q}^{n}$ is the set of coordinate positions where the
coordinates of $w$ are nonzero. The cardinality of the support is the Hamming
weight $\mbox{\rm wt}(w)$ of $w$, so it is equal to the number of its nonzero
coordinates. The _Hamming distance_ between two vectors of
$\mathbb{F}_{q}^{n}$ is defined as the number of coordinates in which they
differ. A _$q$ -ary linear_ $[n,k,d]_{q}$ code is a $k$-dimensional linear
subspace of $\mathbb{F}_{q}^{n}$ with minimum distance $d$. Usually, a linear
code is represented by its generator matrix. The rows of a generator matrix
form a basis of the code as a linear space. Here we use also a representation
of the codes by their characteristic vectors. For more details on the
parameters and properties of linear codes we refer to [9].

###  2.1 Equivalence of linear codes

###### Definition 1

We say that two linear $[n,k]_{q}$ codes $C_{1}$ and $C_{2}$ are equivalent,
if the codewords of $C_{2}$ can be obtained from the codewords of $C_{1}$ via
a finite sequence of transformations of the following types: (1) permutation
of coordinate positions; (2) multiplication of the elements in a given
position by a non-zero element of $\mathbb{F}_{q}$; (3) application of a field
automorphism to the elements in all coordinate positions.

This definition is well motivated as the transformations (1)–(3) preserve the
Hamming distance and the linearity (for more details see [10, Chapter 7.3]).
It is based on the action of the group ${\rm Mon}_{n}(\mathbb{F}_{q})$ of all
monomial $n\times n$ matrices for a prime field and of the semidirect product
${\rm Mon}_{n}(\mathbb{F}_{q})\rtimes{\rm Aut}(\mathbb{F}_{q})$ for a
composite field.

An _automorphism_ of a linear code $C$ is a pair
$(M,\alpha)\in\mathrm{Mon}_{n}(\mathbb{F}_{q})\rtimes\mathrm{Aut}(\mathbb{F}_{q})$
such that $vM\alpha\in C$ for any codeword $v\in C$. The set of all
automorphisms of the code $C$ forms the _automorphism group_
$\mathrm{Aut}(C)$. For binary codes, $\mathrm{Aut}(C)$ consists only of
permutation matrices and can be considered as a subgroup of the symmetric
group $S_{n}$.

Many algorithms for codes use a set of codewords with given properties - to be
invariant with respect to the automorphism group and to generate the code as a
linear space. Usually, this set consists of codewords with weights close to
the minimum weight. The problem of generating such a set is related to two
other problems known as NP-complete – the Weight Distribution Problem [11],
and the Minimum Distance Problem [12]. The complexity of the Code Equivalence
Problem is studied in [13].

We consider the Code Equivalence Problem for linear $q$-ary codes of length
$n$. Leon’s algorithm [4] is based on the group action on a set of $(q-1)n$
points. The algorithm in the package Q-Extension and its successor
QextNewEdition reduces the code equivalence problem to the problem for
isomorphism of binary matrices with $2(q-1)n$ columns. A detailed description
of this representation is given in [14]. In the main algorithm presented here,
we use binary matrices with fewer, most often $n$ columns. For this reason,
the presented algorithm is much more efficient in many cases.

###  2.2 Galois geometries

For the main definitions and theorems as well as more details on Galois
geometries we refer to [15, Section 14.4] and [16].

###### Definition 2

Let $V=V(n+1,\mathbb{F})$, with $n\geq 1$, be an $(n+1)$-dimensional vector
space over the field $\mathbb{F}$ with zero element 0. Define the equivalence
relation $\sim$ on the set of nonzero vectors of $V$: for $v,w\in
V\setminus\\{0\\}$, $v\sim w$ if and only if $w=\alpha v$ for some
$\alpha\in\mathbb{F}$, $\alpha\neq 0$.

(1) The set of equivalence classes is the $n$-dimensional projective space
over $\mathbb{F}$. It is denoted by $\mathrm{PG}(n,\mathbb{F})$ or, when
$\mathbb{F}=\mathbb{F}_{q}$, by $\mathrm{PG}(n,q)$.

(2) The elements of $\mathrm{PG}(n,\mathbb{F})$ are points; the equivalence
class of the vector $X$ is the point $[X]$. The vector $X$ is a coordinate
vector for $[X]$ or $X$ is a vector representing $[X]$. In this case, $\alpha
X$ with $\alpha\in\mathbb{F}\setminus\\{0\\}$ also represents $[X]$, that is,
by definition, $[\alpha X]=[X]$.

(3) If $X=(x_{0},\ldots,x_{n})$ for some basis, then the $x_{i}$ are the
coordinates of the point $[X]$.

(4) The points $[X_{1}],\ldots,[X_{r}]$ are linearly independent if a set of
vectors $X_{1},\ldots,X_{r}$ representing them is linearly independent.

###### Definition 3

Consider $V(n+1,q)$ and its corresponding projective space $\mathrm{PG}(n,q)$.
For any $m=0,1,\ldots,n$, an $m$-dimensional subspace, also called $m$-space,
of $\mathrm{PG}(n,q)$ is a set of points for which the union of all the
corresponding coordinate vectors, together with the zero vector, form an
$(m+1)$-dimensional vector subspace of $V(n+1,q)$.

A $1$-dimensional subspace is called a (projective) line, a $2$-dimensional
subspace is called a (projective) plane, and a $3$-dimensional subspace is
called a (projective) solid. An $(n-1)$-dimensional subspace of
$\mathrm{PG}(n,q)$ is called a hyperplane. An $(n-r)$-dimensional subspace of
$\mathrm{PG}(n,q)$ is also called a subspace of codimension $r$.

In $\mathrm{PG}(n,q)$, every hyperplane is a set of points $[X]$ whose
coordinate vectors $X=(x_{0},\ldots,x_{n})$ satisfy a linear equation

$u_{0}x_{0}+u_{1}x_{1}+\cdots+u_{n}x_{n}=0$

with
$u=(u_{0},\ldots,u_{n})\in\mathbb{F}_{q}^{n+1}\setminus\\{(0,\ldots,0)\\}$,
and is denoted by $\pi(u)$.

###### Definition 4

A collineation $\alpha$ of $\mathrm{PG}(n,q)$, $n\geq 2$, is a bijection which
preserves incidence.

###### Theorem 1

(Fundamental Theorem of Galois Geometry) If $\alpha$ is a collineation of
$\mathrm{PG}(n,q)$, $q=p^{s}$, $p$ prime, $s\geq 1$, then $\alpha$ is a
semilinear bijective transformation of $V(n+1,q)$, i.e., there exists a
nonsingular $(n+1)\times(n+1)$ matrix $A$ over $\mathbb{F}_{q}$ and an
automorphism $\rho:\mathbb{F}_{q}\to\mathbb{F}_{q}$, such that

$\alpha:\left[\begin{array}[]{c}x_{0}\\\ x_{1}\\\ \vdots\\\
x_{n}\end{array}\right]\mapsto A\left[\begin{array}[]{c}\rho(x_{0})\\\
\rho(x_{1})\\\ \vdots\\\ \rho(x_{n})\end{array}\right]$

Let $\mathbb{Z}_{n+1}(q)=\\{\delta:x\mapsto\alpha
I_{n+1}x,\alpha\in\mathbb{F}_{q}\setminus\\{0\\},x\in V(n+1,q)\\}$, where
$I_{n+1}$ is the $(n+1)\times(n+1)$ identity matrix. The projective group of
$\mathrm{PG}(n,q)$, $n\geq 1$, is the group
$\mathrm{PGL}_{n+1}(q)=\mathrm{GL}_{n+1}(q)/\mathbb{Z}_{n+1}(q)$, and the
collineation group of $\mathrm{PG}(n,q)$, $n\geq 1$, is the group
$\mathrm{P\Gamma
L}_{n+1}(q)=\mathrm{PGL}_{n+1}(q)\rtimes\mathrm{Aut}(\mathbb{F}_{q})$.

###### Definition 5

Two sets $S$ and $S^{\prime}$ of spaces contained in $\mathrm{PG}(n,q)$ are
called projectively equivalent to each other if and only if there is a
collineation $\alpha\in\mathrm{P\Gamma L}_{n+1}(q)$ which maps $S$ onto
$S^{\prime}$.

###  2.3 Linear codes and multisets of points

The projective space $\mathrm{PG}(k-1,q)$ contains
$\theta(k-1,q)=\frac{q^{k}-1}{q-1}$ points. For each point $[X]$, take $X$ to
be the coordinate vector, whose first nonzero coordinate is 1 (we call such
vectors normalized), and then order the points lexicographically. We use this
ordering to correspond a characteristic vector to each multiset $M$ of points
in the projective geometry:

$\chi(M)=\left(\chi_{1},\chi_{2},\ldots,\chi_{\theta(k-1,q)}\right)\in\mathbb{Z}^{\theta(k-1,q)}$
(1)

where $\chi_{u}$ shows how many times the $u$-th point of $\mathrm{PG}(k-1,q)$
occurs in $M$, $u=1,\ldots,\theta(k-1,q)$.

There is a direct relation between the linear codes of dimension $k$ over
$\mathbb{F}_{q}$ and the multisets of points in the projective geometry
$\mathrm{PG}(k-1,q)$. Let $G$ be a generator matrix of a $q$-ary linear
$[n,k,d]$ code $C$, and let
$g_{1},g_{2},\ldots,g_{n}\in\mathbb{F}_{q}^{k}=V(k,q)$ be the columns of $G$.
Suppose that none of these columns is the zero vector (then we say that the
code $C$ is of full length). Each vector $g_{i}$ determines a point $[g_{i}]$
in the projective space $\mathrm{PG}(k-1,q)$. If the vectors $g_{i}$ are pair-
wise independent, then $M_{G}=\\{[g_{1}],[g_{2}],...,[g_{n}]\\}$ is a set of
$n$ points in $\mathrm{PG}(k-1,q)$. When dependence occurs, we interpret
$M_{G}$ as a multiset and count each point with the appropriate multiplicity
[17].

On the other hand, if $M$ is a multiset of $n$ points in $\mathrm{PG}(k-1,q)$,
the $k\times n$ matrix $G_{M}$, whose columns are the normalized coordinate
vectors of the points from $M$, generates a linear $[n,k]$ code $C_{M}$. The
minimum distance of $C_{M}$ is equal to $d$ if (a) each hyperplane of
$\mathrm{PG}(k-1,q)$ meets $C_{M}$ in at most $n-d$ points and (b) there is a
hyperplane meeting $C_{M}$ in exactly $n-d$ points. Some authors even give a
definition for linear codes as multisets of points [18]. If the multiset $M$
is a set then we call $C_{M}$ a projective code. Two codes of full length are
equivalent if and only if the corresponding multisets of points are
projectively equivalent [17].

The characteristic vector of the code $C$ with respect to its generator matrix
$G$ is the characteristic vector of the multiset $M_{G}$, or

$\chi(C,G)=\left(\chi_{1},\chi_{2},\ldots,\chi_{\theta(k-1,q)}\right)\in\mathbb{Z}^{\theta(k-1,q)}$
(2)

where $\chi_{u}$ is the number of the columns of $G$ that are coordinate
vectors of the $u$-th point of $\mathrm{PG}(k-1,q)$,
$u=1,\ldots,\theta(k-1,q)$. When $C$ and $G$ are clear from the context, we
will briefly write $\chi$.

A code $C$ can have different characteristic vectors depending on the chosen
generator matrices. If we permute the columns of the matrix $G$ we will obtain
a permutation equivalent code to $C$ having the same characteristic vector.
Moreover, from a characteristic vector one can restore the columns of the
generator matrix $G$ but eventually at different order and/or multiplied by
nonzero elements of the field.

##  3 The algorithms

###  3.1 Algorithm for Code Equivalence using the Incidence Matrix
of Projective Geometry

Denote by $G_{q,k}$ the $k\times\theta(k-1,q)$ matrix whose columns are the
normalized coordinate vectors of the points in $\mathrm{PG}(k-1,q)$ ordered
lexicographically. The rows of $G_{q,k}$ are linearly independent and so it
generates a $q$-ary linear code of dimension $\theta(k-1,q)$ and dimension
$k$. This code is called the simplex code and denoted by $\mathcal{S}_{q,k}$.
Its characteristic vector is $(1,1,\ldots,1)$, and all nonzero codewords of
$\mathcal{S}_{q,k}$ have weight $\theta(k-1,q)/2$.

Further, we consider the matrix $A_{k}=G_{q,k}^{\rm T}\cdot G_{q,k}$. The rows
of this matrix form a maximal set of nonproportional codewords in the
considered simplex code. For the elements of $A_{k}$ we have
$a_{ij}=u_{i}\cdot u_{j}=\sum_{m=1}^{k}u_{mi}u_{mj}$, where $u_{i}\cdot u_{j}$
is the Euclidean inner product of the vectors
$u_{i},u_{j}\in\mathbb{F}_{q}^{k}$ over the field $\mathbb{F}_{q}$. Obviously,
the $i$-th row of the matrix $A_{k}$ can be identified with the hyperplane
$\pi(u_{i})$ with the following equation

$u_{1i}x_{1}+u_{2i}x_{2}+\cdots+u_{ki}x_{k}=0.$

We denote by ${\cal N}(A_{k})$ the matrix obtained from $A_{k}$ by replacing
all nonzero elements by $1$ and call it a normalized matrix. Obviously, ${\cal
N}(A_{k})_{ij}=0$ if and only if the vectors $u_{i}$ and $u_{j}$ are mutually
orthogonal. This can be interpreted in the following way: ${\cal
N}(A_{k})_{ij}=0$ if and only if the point $[u_{j}]$ is incident with the
hyperplane induced by $u_{i}$. If we juxtapose 0’s and 1’s in ${\cal
N}(A_{k})$, we obtain the incidence matrix of the points and hyperplanes in
the projective space $\mathrm{PG}(k-1,q)$. Both matrices have the same
automorphism group which we denote by $\mathrm{Aut}_{k}=\mathrm{Aut}({\cal
N}(A_{k}))$. It consists of the permutations of the columns that preserve the
set of rows of the matrix, so it is a subgroup of the symmetric group
$S_{\theta(k-1,q)}$. Since the automorphism group of a finite incidence
structure acts as permutation group on the points, the automorphism group of
the matrix ${\cal N}(A_{k})$ is isomorphic to $\mathrm{P\Gamma L}_{k}(q)$ and
instead of acting on the points in $\mathrm{PG}(k-1,q)$ or on the columns of
the matrix ${\cal N}(A_{k})$, we can take the action on the characteristic
vectors.

Let $\mathfrak{C}$ be the set of the projective $[n,k]_{q}$ codes. Consider
the action of the group $\mathrm{Aut}_{k}$ on the set $\mathfrak{C}$ as the
codes are represented by their characteristic vectors. Then we have the
following theorem.

###### Theorem 2

Two projective linear $[n,k]_{q}$ codes are equivalent if and only if their
characteristic vectors belong to one orbit under the action of
$\mathrm{Aut}_{k}$ on the set $\mathfrak{C}$.

Proof. According to [17, Proposition 1], two codes of full length are
equivalent if and only if the corresponding multisets of points are
projectively equivalent. On the other hand, two multisets $M_{1}$ and $M_{2}$
are equivalent if and only if there is a permutation $\pi$ that maps the
points of $M_{1}$ to the points of $M_{2}$, which can be applied further to
the characteristic vectors. It turns out that the multisets $M_{1}$ and
$M_{2}$ are equivalent if and only if there is a permutation $\pi$ such that
$\chi(M_{1})\pi=M_{2}$ (the characteristic vectors belongs to one orbit).
$\Box$

Take $C_{i}=C_{M_{i}}$ and $G_{i}$ to be the matrix whose columns are the
normalized coordinate vectors of the points in $M_{i}$, $i=1,2$. Since the
groups $\mathrm{P\Gamma L}_{k}(q)$ and $\mathrm{Aut}_{k}$ are isomorphic, to
the permutation $\pi$ we can correspond a nonsingular matrix
$T_{\pi}\in\mathrm{PGL}(k,q)$ such that $T_{\pi}G_{1}=G_{2}P$ where $P$ is a
permutation matrix that permutes the columns of the $k\times n$ matrix
$G_{2}$.

We present the algorithm for projective linear codes which means that their
corresponding multisets are actually sets of points, and the coordinates of
their characteristic vectors are only 0’s and 1’s.

We apply our program for isomorphism of binary matrices to obtain the
inequivalent codes in the following way:

  1. 1.

to any code $C$ with a characteristic vector $\chi$ with respect to its
generator matrix we correspond the $(\theta(k-1,q)+1)\times\theta(k-1,q)$
matrix $G_{C}=\left(\begin{array}[]{c}{\cal N}(A_{k})\\\
\chi\end{array}\right)$;

  2. 2.

we run the isomorphism test IsBMiso for these matrices.

###### Remark 1

If the codes are not projective, we can add coloring of the columns and then
apply the same algorithm.

###  3.2 Algorithm for Code Equivalence using a Shortened Incidence Matrix of
Projective Geometry

We will describe the algorithm in the case when $q$ is a prime. We use smaller
binary matrices and prove that if these matrices are not isomorphic then the
codes are not equivalent. If these matrices are isomorphic, we use a special
approach to see if the corresponding codes are equivalent.

Instead of the whole matrix $\mathcal{N}(A_{k})$ we take only those columns
that correspond to nonzero coordinates of the considered characteristic vector
$\chi(C,G)$ of the code $C$. The same matrix can be obtained by normalizing
the matrix $A_{G}=A_{k}^{T}G$. The rows of $A_{G}$ are not proportional to
each other and they are nonzero codewords in $C$. Furthermore, any nonzero
codeword in $C$ is proportional to a row-vector of this matrix. Without loss
of generality, we can take the matrix $G$ in systematic form which means that
all column-vectors of weight 1 are columns in $G$. Moreover, we can take the
columns to be normalized vectors.

###### Theorem 3

If the matrices $\mathcal{N}(A_{G_{1}})$ and $\mathcal{N}(A_{G_{2}})$ are not
isomorphic then the codes $C_{1}$ and $C_{2}$ with generator matrices $G_{1}$
and $G_{2}$ are not equivalent.

Proof. Let $\mathcal{N}(A_{G_{1}})\ncong\mathcal{N}(A_{G_{2}})$. Then the
matrices $\mathcal{N}(G_{C_{1}})$ and $\mathcal{N}(G_{C_{2}})$ are not
isomorphic, so the codes $C_{1}$ and $C_{2}$ are not equivalent. $\Box$

Theorem 3 shows that the case
$\mathcal{N}(A_{G_{1}})\ncong\mathcal{N}(A_{G_{2}})$ is clear. Let us now
consider the opposite case, when
$\mathcal{N}(A_{G_{1}})\cong\mathcal{N}(A_{G_{2}})$. Denote the automorphism
group of $\mathcal{N}(A_{G_{1}})$ by $H_{1}$. Recall that the algorithm
IsBMiso tests the binary matrices for isomorphism and computes generating
elements of their automorphism groups. There are two possibilities for $H_{1}$
\- (1) to be trivial or (2) to contain at least two elements.

(1) Let $H_{1}=\\{\epsilon\\}$.

Since the group is trivial, there is a unique permutation $\sigma\in S_{n}$
that maps the rows of $\mathcal{N}(A_{G_{1}})$ into the rows of
$\mathcal{N}(A_{G_{2}})$. The codes are equivalent if there is a monomial
matrix $M_{\sigma}=P_{\sigma}D$ such that $G_{1}M_{\sigma}$ generates the
second code, where $P_{\sigma}$ is the permutation matrix corresponding to
$\sigma$, and $D=\mathrm{diag}(\lambda_{1},\ldots,\lambda_{n})$ is a
nonsingular diagonal matrix. Since $G_{2}$ and $G_{1}M_{\sigma}$ generate the
same code, there is an invertible matrix $Q\in\mathrm{GL}(k,q)$ such that
$QG_{2}=G_{1}M_{\sigma}$. Without loss of generality we can consider $G_{2}$
in the form $(I_{k}|E)$. Hence

$QG_{2}=(Q|QE)=G_{1}M_{\sigma}=G_{1}P_{\sigma}\mathrm{diag}(\lambda_{1},\ldots,\lambda_{n}).$
(3)

The columns of $G_{1}P_{\sigma}$ are the permuted columns of
$G_{1}=(g_{1},g_{2},\dots,g_{n})$. It turns out that
$G_{1}P_{\sigma}D=(\lambda_{1}g_{i_{1}},\ldots,\lambda_{n}g_{i_{n}})$ where
$\sigma^{-1}(s)=i_{s}$, $s=1,\ldots,n$. Hence
$Q=(\lambda_{1}g_{i_{1}},\ldots,\lambda_{k}g_{i_{k}})$. The next step is to
solve the system of linear equations

$QE=(\lambda_{1}g_{i_{1}},\ldots,\lambda_{k}g_{i_{k}})E=(\lambda_{k+1}g_{i_{k+1}},\ldots,\lambda_{n}g_{i_{n}})$

with variables $\lambda_{1},\ldots,\lambda_{n}$. This is a homogeneous system
so it is consistent, but we are looking for a solution in which all entries
are nonzero. Such a solution gives an invertible matrix $Q\in\mathrm{GL}(k,q)$
which maps the first set of points into the second one and then these
multisets and their codes are equivalent. It also means that there is an
automorphism of ${\cal N}(A_{k})$ that maps the characteristic vector of the
code $C_{1}$ to the characteristic vector of the second code.

If no solution has the needed property, the codes are inequivalent.

(2) Let $H_{1}$ is not trivial.

Let $H_{1}=\left\langle\tau_{1},\ldots,\tau_{m}\right\rangle$. We can use two
approaches in the algorithm. In the first one, for each permutation
$\tau_{i}$, we are looking for a nonsingular matrix $Q_{i}$ such that

$Q_{i}G_{1}=G_{1}P_{\tau_{i}}D_{i}=G_{1}P_{\tau_{i}}\mathrm{diag}(\alpha_{i1},\ldots,\alpha_{in})$
(4)

for nonzero elements $\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}_{q}$. If we
have needed solutions of the considered systems of linear equations and have
computed the invertible matrices $Q_{i}$, we go to the last step. The
existence of nonsingular matrices $Q_{i}$ for all $i$ shows that the order of
$\mathrm{Aut}(C_{1})$ is equal to $(q-1)|H_{1}|$. The matrices $Q_{i}$
generate the automorphism group of the corresponding set of points. For the
last step, we need a permutation $\sigma\in S_{n}$ that maps the rows of
$\mathcal{N}(A_{G_{1}})$ into the rows of $\mathcal{N}(A_{G_{2}})$. As in the
case (1), we are looking for an invertible matrix $Q$ such that the system

$QG_{2}=(Q|QE)=G_{1}P_{\sigma}\mathrm{diag}(\lambda_{1},\ldots,\lambda_{n})$

has a solution in which all entries are nonzero.

If for some $\tau_{i}$ the system (4) does not have a solution with nonzero
entries, then we go to the first algorithm.

###### Example 1

Consider the ternary codes $C_{1}$ and $C_{2}$ with generator matrices

$G_{1}=\left[\begin{array}[]{cccccc}1&0&0&1&2&0\\\ 0&1&0&1&1&1\\\
0&0&1&1&1&0\\\ \end{array}\right],\ \ \
G_{2}=\left[\begin{array}[]{cccccc}1&0&0&1&1&0\\\ 0&1&0&1&2&0\\\
0&0&1&1&0&2\\\ \end{array}\right],$

respectively. The permutation $\sigma=(2\ 3\ 4)$ maps the rows of
$\mathcal{N}(A_{G_{1}})$ into the rows of $\mathcal{N}(A_{G_{2}})$. The
automorphism groups of the two matrices are not trivial but we go directly to
the last step of the algorithm, so we are looking for an invertible matrix
$Q\in\mathrm{GL}(3,3)$ such that

$QG_{1}=G_{2}P_{\sigma}\mathrm{diag}(\lambda_{1},\dots,\lambda_{6}).$

This gives the following system of linear equations:

$\begin{array}[]{|rrrl}\lambda_{1}&+\lambda_{2}&&=0\\\
&\lambda_{2}&+\lambda_{3}&=0\\\ &\lambda_{2}&&=\lambda_{4}\\\ \end{array}\ \ \
\ \ \begin{array}[]{|rrrl}\lambda_{1}&+2\lambda_{2}&&=2\lambda_{5}\\\
&2\lambda_{2}&&=\lambda_{5}\\\ &2\lambda_{2}&&=\lambda_{5}\\\ \end{array}\ \ \
\ \ \begin{array}[]{|rrrl}&&0&=0\\\ &&2\lambda_{3}&=\lambda_{6}\\\ &&0&=0\\\
\end{array}.$

The solution is $p(1,2,1,2,1,2)$, $p\in\mathbb{F}_{3}$. Thus we obtain

$Q=\left[\begin{array}[]{ccc}1&2&0\\\ 0&2&1\\\ 0&2&0\end{array}\right].$

It turns out that the two codes are equivalent.

The presented example shows that we can prove that two codes are equivalent
using only the last step in the algorithm. The problem arises when there is no
invertible matrix to satisfy (3). This fact does not prove the inequivalence
of the considered codes and therefore we have to follow the other steps of the
algorithm. It is possible to obtain an invertible matrix that sends the
codewords of $C_{1}$ to codewords of $C_{2}$ from some of the permutations
$\sigma\tau_{i}$, $1\leq i\leq m$. Since we use canonical forms in the program
for isomorphism of binary matrices, even if neither of the permutations
$\sigma,\sigma\tau_{1},\ldots,\sigma\tau_{m}$ produces invertible matrix, the
equivalence of the two codes is still possible. Therefore, in such a situation
we use the first algorithm, namely CEIMPG.

The second approach has the disadvantage that we do not count the automorphism
groups of the codes. If we compare only two codes, this is not important, but
if we have a set with more than a thousand codes, the first approach is more
useful.

###### Remark 2

If the field is composite (when $q=p^{m}$, $p$ \- prime, $m>1$) then the
matrix equation (3) changes to

$QG_{2}=(Q|QE)=G_{1}P_{\sigma}\mathrm{diag}(\lambda_{1},\ldots,\lambda_{n})\rho,$
(5)

where $\rho$ is an automorphism of the field $\mathbb{F}_{q}$. In this case
there are $n$ unknown variables $\lambda_{1},\ldots,\lambda_{n}$ and an
unknown automorphism $\rho$. Recall that the automorphism group of the field
$\mathbb{F}_{q}$ is a cyclic group of order $m$.

##  4 Experimental results

The number of the needed basic operations in the described algorithms depends
on the size of the input data and the structure of the considered codes. There
is a relationship between the structure of the binary matrices that are used
in the algorithms CESIMPG and LCequivalence. If the matrices correspond to
regular combinatorial structures, such as orthogonal arrays, t-designs or
Hadamard matrices, the algorithms need more operations to compute the
automorphism groups, to obtain the canonical forms and to distinguish the
inequivalent codes. In fact, the difference in computational time between the
algorithms comes from the difference in the size of the input data. For
example, if we consider $[24,4]$ codes over $\mathbb{F}_{3}$, the algorithm
CESIMPG uses $40\times 24$ binary matrices, but the matrices in LCequivalence
have size $s\times 84$ where $s$ is the number of codewords in the considered
generating set of the code, so we can expect that the first algorithm will be
faster. Comparing the sizes, we conclude that presented here algorithm is
faster for small dimensions. We present some experimental results in Table 1.
We first generate random codes with given length and dimension (their number
is shown in column 3), then check them for equivalence. The number of
inequivalent codes is given in column 4. In the last two columns we present
the computational time of algorithms CESIMPG and LCequivalence, respectively.

All examples are executed on (Intel Core i7-6700HQ 2.60 GHz processor) in
Active solution configuration — Release, and Active solution platform — X64.
As a development environment for both algorithms we use MS Visual Studio 2019.

In addition, we have to mention that CESIMPG can be further improved in
several directions. For example, for larger fields, many of the rows in the
matrix $A_{G}$ have maximum supports, i.e. their Hamming weights are equal to
the length of the code. After normalization, they go into the all-ones vector
which does not give any information about the automorphism group and the
orbits, and therefore we can remove these rows. The work on this algorithm is
still ongoing and we expect to have better results in the computational time.

Table 1: Experimental results |  |  |  $\sharp$ generated |  $\sharp$ inequivalent |  |
---|---|---|---|---|---|---
$q$ | $k$ | $n$ | codes | codes | CESIMPG | LCequivalence
3 | 3 | 10 | 10 000 | 347 | 0.59s | 2.68s
| 3 | 24 | 10 000 | 8 306 | 1.16s | 71.58s
| 4 | 10 | 10 000 | 1 275 | 1.05s | 2.17s
| 4 | 24 | 10 000 | 10 000 | 1.87s | 14.47s
| 5 | 10 | 10 000 | 1 946 | 1.84s | 2.17s
| 5 | 24 | 10 000 | 10 000 | 3.24s | 8.78s
7 | 3 | 10 | 10 000 | 8 288 | 1.81s | 15.43s
| 3 | 24 | 10 000 | 10 000 | 1.75s | 136s
| 4 | 10 | 1 000 | 999 | 0.56s | 2.38s
| 4 | 24 | 1 000 | 1 000 | 0.65s | 7.55s
| 5 | 10 | 1 000 | 1 000 | 4.79s | 1.69s
| 5 | 24 | 1 000 | 1 000 | 3.79s | 5.88s
11 | 3 | 10 | 10 000 | 9 986 | 5.69s | 37.57s
| 3 | 24 | 10 000 | 10 000 | 2.56s | 335.69s
| 4 | 10 | 1 000 | 1 000 | 2.38s | 5.21s
| 4 | 24 | 1 000 | 1 000 | 1.74s | 21.80s
| 5 | 10 | 1 000 | 1 000 | 27.96s | 3.95s
| 5 | 24 | 1 000 | 1 000 | 30.84s | 16.00s

## Acknowledgements

The research of Stefka Bouyuklieva was supported by a Bulgarian NSF contract
KP-06-N32/2-2019. The research of Iliya Bouyukliev was supported, in part, by
a Bulgarian NSF contract KP-06-Russia/33/17.12.2020.

## References

  * [1] I. Bouyukliev, About the code equivalence, in Advances in Coding Theory and Cryptology, eds. T. Shaska, W. Huffman, D. Joyner and V. Ustimenko, Series on Coding Theory and Cryptology, Vol. 3 (World Scientific, 2007), pp. 126–151.
  * [2] T. Feulner, The automorphism groups of linear codes and canonical representatives of their semilinear isometry classes, Adv. Math. Commun. 3, 363 (2009).
  * [3] N. Sendrier, Finding the permutation between equivalent linear codes: the support splitting algorithm, IEEE Trans. Inform. Theory 46, 1193 (2000).
  * [4] J. Leon, Computing automorphism groups of error-correcting codes, IEEE Trans. Inform. Theory 28, 496 (1982).
  * [5] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24, 235 (1997), Computational algebra and number theory (London, 1993).
  * [6] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.11.0, (2020).
  * [7] B. D. McKay and A. Piperno, Practical graph isomorphism, {II}, J. Symbolic Comput. 60, 94 (2014).
  * [8] I. Bouyukliev, QextNewEdition \- LCequivalence module Online available at http://www.moi.math.bas.bg/moiuser/~data/Software/QextNewEditionLCequiv.html, (2020), Accessed on 2021-01-27.
  * [9] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, Cambridge, UK, 2003).
  * [10] P. Kaski and P. Östergård, Classification algorithms for codes and designs, Algorithms and Computation in Mathematics, Vol. 15 (Springer, 2006).
  * [11] E. Berlekamp, R. McEliece and H. van Tilborg, On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory 24, 384 (1978).
  * [12] A. Vardy, The intractability of computing the minimum distance of a code, IEEE Trans. Inform. Theory 43, 1757 (1997).
  * [13] E. Petrank and R. M. Roth, Is code equivalence easy to decide?, IEEE Trans. Inform. Theory 43, 1602 (1997).
  * [14] I. Bouyukliev and M. Dzhumalieva-Stoeva, Representing equivalence problems for combinatorial objects, Serdica J. Comput. 8, 327 (2014).
  * [15] G. L. Mullen and D. Panario, Handbook of Finite Fields (Chapman and Hall/CRC, Boca Raton, FL 33487-2742, 2013).
  * [16] L. Storme, Coding Theory and Galois Geometries, in Concise Encyclopedia of Coding Theory, eds. W. C. Huffman, J.-L. Kim and P. Solé (CRC Press, 2021), pp. 285–306.
  * [17] S. Dodunekov and J. Simonis, Codes and projective multisets, Electron. J. Combin. 5, p. R37 (1998).
  * [18] I. N. Landjev, Linear codes over finite fields and finite projective geometries, Discrete Math. 213, 211 (2000).