Radio

Writing a factorial function in C

Posted at

TLDR: The most common implementations of the factorial function in C do not handle errors correctly and have typical code vulnerabilities. The factorial function should include error handling even when only for the goal of teaching recursion, so that beginners get used to writing robust code.

Note: If you need a real factorial function, or its logarithm to do number theoretical calculations, it’s available in the C standard library as tgammal() and lgammal() functions [1][2][3].

Hooded hacker at keyboard with binary code in front
According to the 2020 Common Weakness Enumeration (CWE™) Top 25 Most Dangerous Software Weakness list, buffer attacks are the second (out-of-bounds write) and fourth (out-of-bounds read) most dangerous software weaknesses. Improper input validation is third and integer overflow is eleventh.

!☕ The C language was created shortly after the Unix operating system in the 1970’s, so that the new operating system could be written in a simple and efficient programming language, instead of assembly [4]. Portability soon became a motivation too: to be able to run Unix and applications in heterogeneous systems caused the operating system and the C programming language to have a profound and long lasting impact on computer systems [5][6][7][8][9]. Simplicity, efficiency and portability, built into the language and transformed into programming philosophy, came with a price. When programming in C, if you want it, you’ll have it. That includes writing broken code, invoking behavior not defined by the language and, in general, allowing you, without questioning, to “shoot your own foot”. Those who do not program in C might believe this wouldn’t affect them. Remember, though, that many modern languages were influenced and even replicated C syntax and behavior [10]. Even for languages that were not directly influenced by C, simplicity and efficiency requirements may still cause a lot of astonishment.

In this post, we’ll begin by writing a couple of factorial function implementations in C that 9 out of the first 10 Google Search results implement. Then, we’ll discuss the problems, present a minimal robust implementation and finally discuss about different ways of doing error handling in C, so that, in the end you feel motivated to always write robust code.

Recursive factorial

So here we go, this is the “Google version” of the recursive factorial function written in C:

#include <stdio.h>

int factorial(int n)
{
	/* This basic recursive factorial function is widespread
	 * on the Internet, but results in incorrect results most
	 * of the time, contains a stack overflow and integer
	 * underflow. */
	if (n == 0) return 1;

	return n*factorial(n-1);
}

int main(void)
{
	int x;

	/* Missing error checking on standard I/O. */
	printf("Input a number: ");
	scanf("%d", &x);
	printf("The factorial of %d is: %d\n", x, factorial(x));

	return 0;
}

Let’s compile and run this program:

$ cc -o fact0 fact0.c
$ ./fact0
Input a number: 100
The factorial of 100 is: 0
$

So the factorial of 100 is 0. Or is it ? Factorials are positive integers. Have we written anything wrong ? A quick search online shows that there are indeed implementations exactly like this and that the mathematical recursive formula for the factorial is correct. Also, for some numbers the program correctly calculates the result:

$ ./fact0
Input a number: 5
The factorial of 5 is: 120
$ ./fact0
Input a number: 12
The factorial of 12 is: 479001600
$

Interlude: factorial in Python

Let’s put this code on hold for a moment and implement exactly the same algorithm in Python:

#!/usr/bin/env python3
def factorial(n):
    # Incomplete factorial implementation, but better than C
    # (all behavior is defined by the language).
    if n == 0: return 1

    return n*factorial(n-1)

def main():
    x = int(input('Input a number: '))
    print('The factorial of %d is: %d' % (x, factorial(x)))

if __name__ == '__main__': main()

Running this program outputs:

$ ./fact.py
Input a number: 100
The factorial of 100 is: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
$ ./fact.py
Input a number: 5
The factorial of 5 is: 120
$ ./fact.py
Input a number: 12
The factorial of 12 is: 479001600
$

Ok, now it makes sense. The Python programming language, using arbitrary precision integer numbers is able to correctly calculate the factorial using the recursive formula. In the case of C, the integer data type (int) is a fixed width binary integer number (on my computer, a 32-bit integer), without a defined overflow behavior. I can confirm this is causing problems by using the undefined behavior detector library from my C compiler:

$ cc -o fact0 fact0.c -fsanitize=undefined
$ ./fact0
Input a number: 100
fact0.c:10:10: runtime error: signed integer overflow: 13 * 479001600 cannot be represented in type 'int'
The factorial of 100 is: 0
$

So, that’s it, we’ve found it. Not only integer overflow is happening, we’ve confirmed by using the undefined behavior detector that signed integer overflow in C is undefined behavior. Due to the motivation of being small, efficient and portable to write an operating system 50 years ago, the language rules won’t bother considering this case: what happens when an integer operation overflows ? The language states that it’s undefined. Anything is allowed to happen (like crashing the program or exploding a spaceship). The reason for this is that this might be used for some kind of benefit, typically related to performance and compiler simplicity, for a certain type of computer. For example, for my compiler with default flags, integer overflows simply wrap around to the minimum possible value because, when compiled, it results in the fastest possible integer arithmetic code for my machine, and could be used for modular value calculations, if desired. Other computers are free to implement a different behavior, also striving for the fastest performance, if desired. This means that undefined behavior in C is part of the language specification that helps guaranteeing that the language will be both portable and performant in heterogeneous systems. Undefined behavior is arguably one of the reasons C is so widespread for writing high performance system software. Consider, for example, the modern high performance language Rust, praised for its modern safety features [11], and, in my opinion, one of the best contenders for replacing C++ in the near future, also opting to allow silent integer overflows, yet stating that relying on it is considered an error. More commonly nowadays, however, since computers are becoming more homogeneous, the unexpected result will simply cause a bug, without offering any other portability benefit. Worse yet, in our specific case, compiling with default flags mentioned nothing. The programmer was allowed to do that and the C compiler was silent about that.

As buggy as possible

In the latest international C draft standard (ISO C 2017/2018 [12]), undefined behavior is defined as the following:

3.4.3 undefined behavior

behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements

(…)

EXAMPLE An example of undefined behavior is the behavior on integer overflow.

If the C programming language “imposes no requirements” on the behavior of integer overflow, someone must. That someone is you, the programmer. You are allowed to shoot your own foot, but if you’re smart you won’t.

Now any pragmatic programmer would think that this discussion doesn’t really make sense, since the only goal of the recursive factorial function is to teach recursion and only scratch the surface of C programming, so this discussion is meaningless. If that were the whole story I would agree with that too and never waste my time writing this, but the truth is that even though we must keep it simple, we have gone too far:

Einstein“Everything should be made as simple as possible, but not simpler” – Some really smart guy

In the C factorial example we have gone beyond as simple as possible and the code has become oversimplified and thus incorrect. What I’m talking about is the amount of program failures caused by buffer overflows, rounding errors, uninitialized memory access, insufficient input validations and others that are main causes of electronic device misbehaviors and exploitations in modern information technology. Famous bugs include the $370 million Ariane 5 rocket explosion [13] and the Year 2000 bug [14], both caused by numeric overflows. Less impactful were the integer overflows caused by the addictive Gangnam Style music video being viewed more than 2^31 times on YouTube [15] and Paypal depositing $92 quadrillion (2^63 dollars) into the account of a user [16]. On the other hand, the cyberwarfare Stuxnet virus, believed to have been created by the Israeli and American governments to damage Iranian uranium enrichment centrifuges [17], was able to successfully spread by using a kind of improper input validation when displaying Windows shortcut files and receiving Windows Print Spooler commands, that allowed executing code where there should be only non-verified data (thus, the vulnerability is called remote code execution).

Yearly lists of most dangerous software errors, besides misconfiguration and weak security practices, always include out-of-bounds accesses, NULL pointer dereference, improper input validation and use after freeing dynamic memory [18][19][20]. These errors are allowed by the C language, so it’s the programmer’s task to avoid them. If these fall in the top list of most dangerous software errors, first of all it means they are difficult to avoid even for skilled programmers and second, programmers are not trained well enough to avoid them. So, every time a C program is written, even a simple factorial program, it’s the right moment to reinforce that.

Where the error was

So now let’s go back to the factorial function in C and try to fix it. The first and most important fix is that the program should not crash:

$ ./fact0
Input a number: 1000000
Segmentation fault (core dumped)
$

Did you notice this bug the first time you saw the recursive factorial implementation in C ? That’s already enough for a user to perform a denial-of-service attack on your code. If you’re doing a boundless amount of recursive iterations you’ll inevitably generate a stack overflow. Fortunately, this seems to be a concept easy to grasp and most code available online will replace the unbounded recursion with a manually managed stack or tail recursion elimination, if possible. In the case of the trivial factorial function, we can’t use tail recursion and manual stack management would be out of scope. A better choice would be to implement the iterative version. Just for completeness, since the goal of the factorial function is to teach recursion, we can solve it simply by handling user input validation. In the code, we also add a recursion depth limit, but it won’t really be reached, because the valid input range is really small:

#include <stdio.h>

/* Factorial not defined for negative integers. */
#define FACTORIAL_MIN 0
/* Limit for 32-bit signed integer. */
#define FACTORIAL_MAX 12
/* Recursion limit won't be reached in this case because the valid
 * input range is too small. */
#define RECURSION_LIMIT 1000

int factorial(int n)
{
	/* Correct recursive factorial implementation without stack
	 * overflows. Returns zero on any error. */
	if (n < FACTORIAL_MIN || n > FACTORIAL_MAX) return 0;
	if (n > RECURSION_LIMIT) return 0;

	if (n == 0) return 1;

	return n*factorial(n-1);
}

int main(void)
{
	int x;

	/* Missing error checking on standard I/O. */
	printf("Input a number: ");
	scanf("%d", &x);
	/* Missing error checking when calling the factorial function. */
	printf("The factorial of %d is: %d\n", x, factorial(x));

	return 0;
}

An interesting thing about this code is that we started admitting the return of an error value, in this example, zero, to tell the calling function if the result could actually be computed or not. And that should have been done since the beginning, that is, this simple recursive factorial function can fail. If the function could fail, where was the error handling in the original version ? There was none. This means the original code was broken.

Compiling it with the undefined behavior sanitizer and running it gives the following:

$ cc -o fact0-bounds fact0-bounds.c -fsanitize=undefined
$ ./fact0-bounds
Input a number: 1000000
The factorial of 1000000 is: 0
$ ./fact0-bounds
Input a number: 20
The factorial of 20 is: 0
$ ./fact0-bounds
Input a number: 12
The factorial of 12 is: 479001600
$ ./fact0-bounds
Input a number: -10
The factorial of -10 is: 0
$ 

So, what do we have here ? We’ve fixed the basic factorial function by adding 3 constants and 2 lines of code. That was easy, right ? This example explicitly shows that there are no excuses for not writing robust code.

Results are still incorrect, since zero is returned sometimes, but that’s missing error handling at the caller, not at the factorial function anymore. Also, more advanced developers will notice that this code is platform-dependent, since the valid input range varies with the size of the int data type and the value 12 used for FACTORIAL_MAX requires 32-bit integers. In this particular case it’s not trivial to fix it (the most accurate version requires discovering the reverse factorial of INT_MAX of the target platform during build), but, in general, writing portable code is easy, with help from the build system and portable libraries, and, unlike input validation and writing correct code, writing portable code can be learned with time. Writing correct code, on the other hand, must be learned from the beginning.

Iterative factorial

Let’s continue solving the remaining problems with the most common iterative solution available online. Here it is:

#include <stdio.h>

int factorial(int n)
{
	int i, f;

	f = 1;

	/* The simple iterative function factorial function might
	 * have the following loop form. It contains undefined
	 * behavior and/or infinite loop. */
	for (i = 1; i <= n; i++)
		f *= i;

	return f;
}

int main(void)
{
	int x;

	/* Missing error checking on standard I/O. */
	printf("Input a number: ");
	scanf("%d", &x);
	printf("The factorial of %d is: %d\n", x, factorial(x));

	return 0;
}

Compiling and testing gives the following:

$ cc -o fact1 fact1.c -fsanitize=undefined
$ ./fact1
Input a number: 2147483647
fact1.c:13:5: runtime error: signed integer overflow: 479001600 * 13 cannot be represented in type 'int'
fact1.c:12:23: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'
^C
$

Here, I have input the INT_MAX value (2147483647). The execution didn’t finish, I had to interrupt it because it was stuck in an infinite loop. Besides the same runtime error message with the integer overflow on the factorial calculation, now there’s a second error, on line 12, where the loop iterator is incremented. This happened because the loop allowed the iterator i to be incremented when its value was INT_MAX. The C language allows incrementing past INT_MAX, but the behavior is undefined. The result in my case was that INT_MAX+1 became INT_MIN and the loop condition i <= n (== INT_MAX) is always true, because any int will always be less than or equal to INT_MAX.

The conclusion here is that not only user input must be validated to be within range, arithmetic calculations with bounded values create their own range requirements and must be considered too. A Google engineer once wrote a blog post that stated that nearly all binary searches and mergesorts were broken [21]: they used the calculation (low + high) / 2 to find the middle element of an array without handling the case where low + high would overflow.

In this particular case, it’s surprising to notice that it’s never possible to implement a loop in C with a less than or equal condition (i <= n) if the end of range value is not validated. Maybe it might be useful to always try to use an exclusive comparison operator (less than < or greater than >), but you can’t get away from not validating ranges: if your loop variable increments by 16, then it’s not possible for n to be larger than INT_MAX-16, since any such value, if allowed would also overflow.

There are multiple ways to fix this, like using variable substitution (in this case, iterate over j = i-1 and then set i = j+1 in the loop body) and unrolling one of the loop iterations. I’ll show two ways here, first one reminds of the recursive version, which starts with n and counts backwards:

#include <stdio.h>

int factorial(int n)
{
	int f;

	f = 1;

	/* A factorial function that does not loop forever
	 * (but still overflows). */
	while (n > 0) {
		f *= n;
		n--;
	}

	return f;
}

int main(void)
{
	int x;

	/* Missing error checking on standard I/O. */
	printf("Input a number: ");
	scanf("%d", &x);
	printf("The factorial of %d is: %d\n", x, factorial(x));

	return 0;
}

Compiling and testing it gives the following:

$ cc -o fact1-backwards fact1-backwards.c -fsanitize=undefined
$ ./fact1-backwards 
Input a number: 2147483647 
fact1-backwards.c:12:5: runtime error: signed integer overflow: 2147483647 * 2147483646 cannot be represented in type 'int'
The factorial of 2147483647 is: 0
$ ./fact1-backwards 
Input a number: 5
The factorial of 5 is: 120
$ 

This implementation takes a long time to execute, but it eventually finishes. So, the output shows only one warning from the sanitizer, instead of two, because we solved the bug with the iterator, and now the original overflow bug is the only one left. Let’s move straight ahead to the most general solution, which is to consider the corner case of the positive iteration version as an additional base case:

#include <limits.h>
#include <stdio.h>

/* Factorial not defined for negative integers. */
#define FACTORIAL_MIN 0
/* Limit for 32-bit signed integer. */
#define FACTORIAL_MAX 12

int factorial(int n)
{
	int i, f;

	f = 1;

	/* Correct recursive factorial implementation without integer
	 * overflows. Returns zero on any error. */
	if (n < FACTORIAL_MIN || n > FACTORIAL_MAX) return 0;
	/* Invalid loop bounds has now become a special case. Since it's
	 * already covered by input validation, the line below can be
	 * eliminated. */
	if (n == INT_MAX) return 0;

	for (i = 1; i <= n; i++)
		f *= i;

	return f;
}

int main(void)
{
	int x;

	/* Missing error checking on standard I/O. */
	printf("Input a number: ");
	scanf("%d", &x);
	/* Missing error checking when calling the factorial function. */
	printf("The factorial of %d is: %d\n", x, factorial(x));

	return 0;
}

Compiling and testing it gives the following:

$ cc -o fact1-bounds fact1-bounds.c -fsanitize=undefined
$ ./fact1-bounds 
Input a number: 2147483647
The factorial of 2147483647 is: 0
$ ./fact1-bounds 
Input a number: 20
The factorial of 20 is: 0
$ ./fact1-bounds 
Input a number: -10
The factorial of -10 is: 0
$ ./fact1-bounds 
Input a number: 12
The factorial of 12 is: 479001600

This finally removes all overflows from the iterative version and produces an almost correct full program, except for not informing the user about domain errors and returning zero instead. The most interesting part of this example is to show the powerful effect that user input validation may have on the rest of the program: it’s only a single line and, in this particular case, it even handles the corner case with the loose end: inputting the INT_MAX value is refused by validating the input domain, which is limited to FACTORIAL_MAX, or 12. But off course, this is no excuse to avoid identifying corner cases present in the program, and in other cases user input validation might not be enough.

Next steps

At this point, the task of writing a factorial function in C is complete. By simply adding a couple of lines to the code, we were able to keep the main structure of famous code examples, yet the profound difference is that of a broken versus a correct implementation. Everything should be made as simple as possible, but not simpler, and we made it as simple as possible, avoiding making it vulnerable. The next steps now move on to the more general topic of error handling in C, including how to better communicate both with the developers and the users about the programmer’s intentions and results. See you next post and, by the way, why not try to add error handling to the main() functions above ?

References

  1. The GNU C Library – Special Functions (The GNU C Library)
  2. The Open Group Base Specifications Issue 7, 2018 edition – tgamma
  3. The Open Group Base Specifications Issue 7, 2018 edition – lgamma
  4. Dennies M. Ritchie – The Development of the C Language
  5. TIOBE – TIOBE Index for January 2021
  6. Stack Overflow Insights – Stack Overflow Developer Survey 2020 - Most Popular Technologies
  7. Toptal – After All These Years, the World is Still Powered by C Programming
  8. Bell Labs – The Creation of the UNIX* Operating System
  9. The Open Group Blog – The Unix® Evolution: An Innovative History
  10. Wikipedia – List of C-family programming languages
  11. Microsoft Security Response Center – Why Rust for safe systems programming
  12. ISO/IEC JTC1/SC22/WG14 - C – ISO/IEC 9899:2017 Programming Languages – C
  13. WIRED – History’s Worst Software Bugs
  14. Wikipedia – Year 2000 problem
  15. BBC News – Gangnam Style music video ‘broke’ YouTube view limit
  16. CNN – PayPal accidentally credits man $92 quadrillion
  17. Wikipedia – Stuxnet
  18. CWE - Common Weakness Enumeration – 2020 CWE Top 25 Most Dangerous Software Weaknesses
  19. CWE - Common Weakness Enumeration – 2019 CWE Top 25 Most Dangerous Software Errors
  20. CISA – Alert (AA20-133A) Top 10 Routinely Exploited Vulnerabilities
  21. Google AI Blog – Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken