I did a program in c to do some avl sorting. the program runs well when i test it with no crash. however i ran the program for possible bugs with afl fuzzer and i dont seem to know why i keep getting segmentation fault. below is the tree.c. I dont get bugs when i fuzz without my main.c connecting to the tree.c. Only comes when i send inputs to the tree sorter. Some certain inputs brings about this bug. i made changes to memory allocation but still cant figure out why. i used valgrind, cppcheck and dont get any errors on them. Please why does this error happen and how can i fix it?
an example input from the fuzzer that brings code to segmentation fault
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
I managed to reproduce SIGSEGV in gdb. It is hapened in function rightPermutation, which does not check if pointer to left is NULL or not:
void rightPermutation(Tree* tree, Node* node) {
Node* newNode = node->right;
node->right = newNode->left;
In case the node->left is NULL, you will get SIGSEGV on next line:
node->right->right = newNode;
Further, you can see details of the message and data of the Node structure.
Program received signal SIGSEGV, Segmentation fault. 0x000055555555570c in rightPermutation (tree=0x555555758280, node=0x555555758d20) at tree.c:322 322 node->right->right = newNode; (gdb) p node $1 = (Node *) 0x555555758d20 (gdb) p *node $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, name = 0x555555758d00 ""}