为什么 afl fuzzer 会出现分段错误？

Question

我用 c 编写了一个程序来进行一些 avl 排序。当我测试它没有崩溃时，程序运行良好。但是我运行该程序可能存在 afl fuzzer 的错误，我似乎不知道为什么我总是遇到分段错误。下面是 tree.c。在 main.c 未连接到 tree.c 的情况下进行模糊测试时，我不会遇到错误。只有当我将输入发送到树分类器时才会出现。某些特定的输入会导致此错误。我对内存分配进行了更改，但仍然无法弄清楚原因。我使用了 valgrind、cppcheck，但没有发现任何错误。请问为什么会出现这个错误，我该如何解决？

来自模糊器的示例输入将代码引入分段错误

i 3o
i 7ÿo
i
i 3ÿo
i3
3
i 3ÿ3
i83 3
i23ÿo

tree.c

#include "tree.h"

Tree* tree_create(){
    Tree *tree = malloc(sizeof(Tree));
    tree->root = NULL;

    return tree;
}

void tree_node_delete(Node* node) {
    if (node == NULL) {
        free(node);
        return;
    }

    if (node->left) {
        tree_node_delete(node->left);
    }
    if (node->right) {
        tree_node_delete(node->right);
    }
    free(node->name);
    free(node);


}

void tree_delete(Tree* tree) {
    tree_node_delete(tree->root);
    free(tree);
}

void node_insert(Node* node, int age, char* name, int gen) {
    if (age <= node->age){
        if (node->left == NULL){
            Node* newLeft = calloc(1, sizeof(Node));
            newLeft->age = age;
            newLeft->name = name;
            newLeft->parent = node;
            newLeft->right = NULL;
            newLeft->left = NULL;
            newLeft->isRight = false;
            node->left = newLeft;
        } else {
            node_insert(node->left, age, name, node->left->generation);
        }
    } else {
        if (node->right == NULL){
            Node* newRight = calloc(1, sizeof(Node));
            newRight->age = age;
            newRight->name = name;
            newRight->parent = node;
            newRight->right = NULL;
            newRight->left = NULL;
            newRight->isRight = true;
            node->right = newRight;

        } else {
            node_insert(node->right, age, name, node->right->generation);
        }
    }
}

void tree_insert(Tree* tree, int age, char* name) {
    if (tree->root == NULL) {
        Node *node = calloc(1, sizeof(Node));
        node->name = name;
        node->age = age;
        node->isRoot = true;
        node->right = NULL;
        node->left = NULL;
        tree->root = node;

    } else {
        node_insert(tree->root, age, name, 1);
    }
}

void tree_erase(Tree* tree, int age, char* name) {
    Node* data = tree_find(tree, age, name);
    if (data == NULL) {
        printf("\nThis node doesn't exist in the current tree\n");
    } else {

        data->name = NULL;
        data->age = NULL;
        if (data->grandparent) {
            if(data == data->grandparent->grandchildRR) {
                data->grandparent->grandchildRR = NULL;
            } else  if(data == data->grandparent->grandchildRL) {
                data->grandparent->grandchildRL = NULL;
            } else  if(data == data->grandparent->grandchildLR) {
                data->grandparent->grandchildLR = NULL;
            } else  if(data == data->grandparent->grandchildLL) {
                data->grandparent->grandchildLL = NULL;
            }
        }

        tree_cleanup(tree, &tree->root, tree->root);
    }
}

// Will clean the tree to release previously used nodes
void tree_cleanup(Tree* tree, Node** nodeAdress, Node* node) {
    if (node->left) {
        tree_cleanup(tree, &node->left, node->left);
    }
    if (node->right) {
       tree_cleanup(tree, &node->right, node->right);
    }

    if(node->age == NULL && node->name == NULL) {
         *nodeAdress = NULL;
      free(*nodeAdress);
    }

    if(node->left == NULL && node->grandchildLL) {
        node->left = node->grandchildLL;
        node->left->parent = node;
        node->left->grandparent = node->parent;
        if(node->left->left) {
            node->grandchildLL = node->left->left;
        } else {
            node->grandchildLL = NULL;
        }

    } else if(node->right == NULL && node->grandchildRL) {
        node->right = node->grandchildRL;
        node->right->parent = node;
        node->right->grandparent = node->parent;
        node->right->isRight = true;
        if(node->right->left) {
            node->grandchildRL = node->right->left;
        } else {
            node->grandchildLR = NULL;
        }

    } else if(node->left == NULL && node->grandchildLR) {
        node->left = node->grandchildLR;
        node->left->parent = node;
        node->left->grandparent = node->parent;
        node->left->isRight = false;
        if (node->left->right) {
            node->grandchildLR = node->left->right;
        } else {
            node->grandchildLR = NULL;
        }

    } else if(node->right == NULL && node->grandchildRR) {
        node->right = node->grandchildRR;
        node->right->parent = node;
        node->right->grandparent = node->parent;
        if (node->right->right) {
            node->grandchildRR = node->right->right;
        } else {
            node->grandchildRR = NULL;
        }

    }
}

//Calculate the weight and the balance factor of the node.
void tree_balance_factor(Tree* tree, Node* node) {
    if (node == NULL) {
        return;
    }
    if (node->left) {
        tree_balance_factor(tree, node->left);
    }
    if (node->right) {
        tree_balance_factor(tree, node->right);
    }

    if (node->parent) {
        if (node->isRight == true) {
            if (node->weightRight > node->weightLeft) {
                node->parent->weightRight = node->weightRight+1;
            } else {
                node->parent->weightRight = node->weightLeft+1;
            }

        } else if (node->isRight == false) {
            if (node->weightRight > node->weightLeft) {
                node->parent->weightLeft = node->weightRight+1;
            } else {
                node->parent->weightLeft = node->weightLeft+1;
            }
        }
    }

    node->balancefactor = node->weightRight - node->weightLeft;

    if (node->balancefactor == 2) {
        if(node->right->balancefactor == 1) {
            leftRotation(tree, node);
        } else {
            rightPermutation(tree, node);
            leftRotation(tree, node);
        }

    } else if (node->balancefactor == -2) {
        if(node->left->balancefactor == -1) {
            rightRotation(tree, node);
        } else {
            leftPermutation(tree, node);
            rightRotation(tree, node);
        }

    }
}

// Reset the weightings and set up the grandchilds and grandparents relations back
void tree_balance_factor_reset(Tree* tree, Node* node) {
    if (node == NULL) {
        return;
    }
    if (node->left) {
        tree_balance_factor_reset(tree, node->left);
    }
    if (node->right) {
        tree_balance_factor_reset(tree, node->right);
    }

    node->weightLeft = 0;
    node->weightRight = 0;

    if(node->right) {
        if(node->right->right) {
            node->grandchildRR = node->right->right;
            node->right->parent = node;
            node->right->right->grandparent = node;
        } else {
            node->grandchildRR = NULL;
        }

        if(node->right->left) {
            node->grandchildRL = node->right->left;
            node->right->parent = node;
            node->right->left->grandparent = node;
        } else {
            node->grandchildRL = NULL;
        }
    }

    if(node->left) {
        if(node->left->left) {
            node->grandchildLL = node->left->left;
            node->left->parent = node;
            node->left->left->grandparent = node;
        } else {
            node->grandchildLL = NULL;
        }

        if (node->left->right) {
            node ->grandchildLR = node->left->right;
            node->left->parent = node;
            node->left->right->grandparent = node;
        } else {
            node->grandchildLR = NULL;
        }
    }

}
void setGen (Node* node) {

    if(node->parent) {
        node->generation = node->parent->generation +1;
    }

    if (node->left) {
        setGen(node->left);
    }
    if (node->right) {
        setGen(node->right);
    }
}

void leftRotation(Tree* tree, Node* node ) {
    Node* newNode = node->right;
    if(node->isRoot == true) {
        tree->root = newNode;
        newNode->isRoot = true;
        node->isRoot = false;
        newNode->parent = NULL;
    } else if (node->isRoot = false){
        newNode->parent = node->parent;
        if(node->isRight) {
            newNode->parent->right = newNode;
        } else {
            newNode->parent->left = newNode;
        }
    }
    newNode->left = node;
    node->parent = newNode;
    node->right = NULL;
}

void rightRotation(Tree* tree, Node* node) {
    Node* newNode = node->left;
    if(node->isRoot == true) {
        tree->root = newNode;
        newNode->isRoot = true;
        node->isRoot = false;
        newNode->parent = NULL;
    } else {
        newNode->parent = node->parent;
        if(node->isRight) {
            newNode->parent->right = newNode;
        } else {
            newNode->parent->left = newNode;
        }
    }
    newNode->right = node;
    node->parent = newNode;
    node->left = NULL;
}

void rightPermutation(Tree* tree, Node* node) {
    Node* newNode = node->right;
    node->right = newNode->left;
    node->right->right = newNode;
    newNode->left = NULL;
    newNode->parent = node->right;
    node->right->parent = node;
}

void leftPermutation(Tree* tree, Node* node) {
    Node* newNode = node->left;
    node->left = newNode->right;
    node->left->left = newNode;
    newNode->right = NULL;
    newNode->parent = node->left;
    node->left->parent = node;
}

void tree_print_node(Node* node){
    if (node == NULL) {
        printf("null");
        return;
    }

    printf("[");
    printf("{\"%d\":\"%s\"},", node->age, node->name);
    tree_print_node(node->left);
    printf(",");
    tree_print_node(node->right);
    printf("]");
}

void tree_print(Tree* tree, int printNewline){
    if (tree == NULL) {
        printf("null");
        return;
    }

    tree_print_node(tree->root);

    if (printNewline){
        printf("\n");
    }
}

Node* node_find(Node* node, int age, char* name) {
    int i = strcmp(node->name, name);

    if (node->age == age && i == 0) {
        return node;
    }

    if (age <= node->age) {
        if (node->left) {
            return node_find(node->left, age, name);
        } else {
            return NULL;
        }

    } else {
        if (node->right) {
            return node_find(node->right, age, name);
        } else {
            return NULL;
        }

    }
}

Node* tree_find(Tree* tree, int age, char* name) {
    if(tree->root != NULL) {
        return node_find(tree->root, age, name);
    } else {
        printf("\nNo node inserted in the tree yet\n");
        return NULL;
    }

}

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "main.h"
#include "tree.h"

int main() {
    char* commandBuffer = (char*)malloc(sizeof(char) * 20);
    Tree *tree = tree_create();


    for(;;) {

        if (tree == NULL){
            tree = tree_create();
        }
        tree_balance_factor_reset(tree, tree->root);
        tree_balance_factor(tree, tree->root);
        tree_balance_factor_reset(tree, tree->root);

        printf("\n- Enter <i age name> to insert a node in the tree \n- Enter <e age name> to erase a node \n- Enter <c age name> to check the tree \n- Enter <p> to "
               "print the tree \n- Enter <x> the delete the tree \n- Enter <q> to exit the program\n\n" );

        fgets(commandBuffer, 20, stdin);

        int b = strlen(commandBuffer);
        if(b>=19) {
            int clearVar;
            while (((clearVar = getchar()) != '\n' && clearVar != EOF)) {
        }
        };

        // Quit on EOF or 'q'
        if (feof(stdin) || *commandBuffer == 'q' ){
            break;
        }

        tree = handleString(commandBuffer, tree);

    };

    free(tree);
    free(commandBuffer);

    return 0;
}


Tree* handleString(char command[], Tree *tree){

    if (command == NULL){
        fprintf(stderr, "Invalid command; null pointer\n");
        return tree;
    }

    switch(command[0]){
        case 'i':
            insert(command, tree);
            break;
        case 'e':
            erase(command, tree);
            break;
        case 'c':
            check(command, tree);
            break;
        case 'p':
            tree_print(tree, 1);
            break;
        case 'x':
            tree_delete(tree);
            return NULL;
        default:
            fprintf(stderr, "Invalid command string: %s\n", command);
            break;
    }

    return tree;
}

Tree* insert(char* command, Tree* tree) {
    int age;
    char* name = malloc(sizeof(char) * 20);

    if (2 != sscanf(command, "i %d %19s", &age, name)){
        fprintf(stderr, "Failed to parse insert command: not enough parameters filled\n");
       // return NULL;
    }

    if (tree == NULL){
        tree = tree_create();
    }

    tree_insert(tree, age, name);

    return tree;
}

int erase(char* command, Tree* tree) {
    int age;
    char* name = malloc(sizeof(char) * 20);

    if (2 != sscanf(command, "e %d %19s", &age, name)){
        fprintf(stderr, "Failed to parse erase command: not enough parameters filled\n");
       // return 0;
    }
    tree_erase(tree, age, name);
    return 0;
}

void check(char* command, Tree* tree) {
    int age;
    char* name = malloc(sizeof(char) * 20);

    if (2 != sscanf(command, "c %d %19s", &age, name)){
        fprintf(stderr, "Failed to parse check command\n");
    }

    Node* result = tree_find(tree, age, name);
    if (result){
        printf("\nThe node is present\n");
    } else {
        printf("\nThe node could not be found\n");
    }
}

tree.h

#ifndef C_IMPLEMENTATION_TREE_H
#define C_IMPLEMENTATION_TREE_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct Node {
    /**
     * Left child of this node
     */
    struct Node* left;
    /**
     * Right child of this node
     */
    struct Node* right;
    /**
     * The age of the data in this node
     */
    int generation;
    int balancefactor;

    int weightLeft;
    int weightRight;

    struct Node* parent;
    struct Node* grandparent;
    struct Node* grandchildLL;
    struct Node* grandchildLR;
    struct Node* grandchildRL;
    struct Node* grandchildRR;


    bool isRight;
    bool parentIsRight;
    bool isRoot;
    int age;
    /**
     * The name of the data in this node
     */
    char* name;
} Node;


typedef struct Tree {
    Node *root;
} Tree;

/**
 * Create a new tree
 * @param age The age value for the first data point
 * @param name The name value for the first data point
 * @return The root Node of the tree
 */
Tree* tree_create();

/**
 * Delete an entire tree. This will delete the passed Node and all children below it
 * @param node The root Node of the tree to delete.
 */
void tree_delete(Tree* tree);

/**
 * Insert a new data point into the tree
 *
 * @param tree The root node of the tree
 * @param age The age part of the data point
 * @param name The name part of the data point
 */
void tree_insert(Tree* tree, int age, char* name);

/**
 * Remove a data point from a tree
 * @param tree The root node of the tree
 * @param age The age part of the data point to delete
 * @param name The name part of the data point to delete
 */
void tree_erase(Tree* tree, int age, char* name);

/**
 * Prints a tree in the following format:
 * [<data>, <left>, <right>]
 * where the elements above have the following format:
 *  <data>             {<age:int>: "<name:string>"}
 *  <left>, <right>:   The same format as the root node. When a child node is NULL, the string NULL is to be printed.
 */

void tree_cleanup(Tree* tree, Node** nodeAdress, Node* node);
    /**
     * Will free and release null nodes.
     */
void setGen(Node* node);

void tree_balance_factor(Tree* tree,Node* node);

void tree_balance_factor_reset(Tree* tree, Node* node);

void leftRotation(Tree* tree, Node* node);

void rightRotation(Tree* tree,Node* node);

void rightPermutation(Tree* tree, Node* node);

void leftPermutation(Tree* tree, Node* node);

void tree_print(Tree *tree, int printNewline);

Node* tree_find(Tree* node, int age, char* name);

#endif //C_IMPLEMENTATION_TREE_H

Answer 1

我设法在 gdb 中重现了 SIGSEGV。它在函数 rightPermutation 中发生，它不检查指向左的指针是否为 NULL:

void rightPermutation(Tree* tree, Node* node) {
    Node* newNode = node->right;
    node->right = newNode->left;

如果 node->left 为 NULL，您将在下一行收到 SIGSEGV：

node->right->right = newNode;

此外，您还可以看到Node结构的消息和数据的详细信息。

程序收到信号 SIGSEGV，分段错误。右排列中的 0x000055555555570c（树=0x555555758280，节点=0x555555758d20）在 tree.c:322 322节点->右->右=新节点； (gdb) p 节点 $1 = (节点 *) 0x555555758d20 (gdb) p *节点 $2 = {left = 0x555555758ed0, right = 0x0, generation = 0, balancefactor = 2, weightLeft = 1, weightRight = 3, parent = 0x0, grandparent = 0x555555758b70, grandchildLL = 0x0, grandchildLR = 0x0, grandchildRL = 0x0, grandchildRR = 0x555555758c00, isRight = false, parentIsRight = false, isRoot = true, age = 0, 名称 = 0x555555758d00 ""}

为什么 afl fuzzer 会出现分段错误？

Why does afl fuzzer get segmentation fault?

c

security

fuzzing

segmentation-fault

american-fuzzy-lop