Created
February 27, 2014 21:48
-
-
Save jasoncausey/9260279 to your computer and use it in GitHub Desktop.
In preparation for a class-related discussion of the Apple "goto fail" bug, I wanted to be able to talk about why the `if-goto-label` construct was used in the original source, and also look at some alternatives that are more structured. This program shows the original goto-based structure in a simplifed (and corrected) form, and compares it (th…
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* @file goto_fail_fix_timings.cpp | |
* | |
* This program reproduces the "if-goto-label" structure | |
* that was employed in Apple's sslKeyExchange.c in the | |
* SSLVerifySignedServerKeyExchange() function | |
* made infamous in the Apple "goto fail" security | |
* bug to see how much of a performance advantage was gained | |
* from using if-goto-label versus a more structured solution | |
* such as if-else chains or a single logical expression | |
* using the `&&` operator. | |
* | |
* These tree constructs are provided below, and timing | |
* trials are run for all three, given simulated function | |
* calls that either return values directly or compute | |
* some mathematical functions to simulate the complexity | |
* of the MD5 and SHA1 hashing that is being done in the | |
* original. | |
* | |
* The results show the following (on my system, an iMac | |
* running a 2.9GHz Intel Core i5): | |
* | |
* Under no load (the STRUCTURE_ONLY option is activated): | |
* When all function calls succeed: | |
* The `goto` performs around 0.5 - 5% better than the | |
* `&&` version (which performs around 10-17% better than | |
* the if-else chain on cases where all function calls succeed). | |
* On an early failure (`foo()` fails): | |
* `goto` performs ~45% better than `&&`, but the | |
* if-else chain actually performs only <~10% worse | |
* than `goto`. This is counter-intuitive since the | |
* `&&` should also have had the same short-circuit | |
* behavior as the if-else chain... | |
* | |
* Under a simulated load (comment out STRUCTURE_ONLY): | |
* When all function calls succeed: | |
* Less than 0.3% difference between all three trials. | |
* (This seems to be within the range of "noise" on my | |
* machine, so essentially there is no discernable | |
* difference.) | |
* On an early failure (`foo()` fails): | |
* Again, the difference seems to stay < ~0.3%, which | |
* puts it within the noise on my test machine... | |
* No discernable difference. | |
* | |
* Discussion of Results: | |
* While the `goto` construct does perform slightly better | |
* than the more structured solutions strictly speaking, | |
* any advantage would be far outweighed by the performance | |
* of the hashing functions themselves -- there is no | |
* discernable advantage to using `goto` here instead of a | |
* more structured control structure. | |
* | |
* Additionally, since you would assume the "normal" case | |
* is that all checks would succeed (most sites are really | |
* who they say they are), the more significant advantage | |
* shown by the `goto` under the "early out" condition would | |
* be realized only in rare cases. If you were "optimizing | |
* for the common case", the `goto` offers no significant | |
* advantage. | |
* | |
* | |
* @author Jason Causey | |
* Arkansas State University | |
* Department of Computer Science | |
* | |
* @copyright Jason Causey 2014, | |
* released under the MIT License: | |
* http://opensource.org/licenses/MIT | |
*/ | |
#include<iostream> | |
using std::cout; | |
using std::endl; | |
#include<ctime> | |
#include<cmath> | |
#include<cstdlib> | |
#include<iomanip> | |
// Comment the following line to add a simulated | |
// "load" to the function calls: | |
#define STRUCTURE_ONLY | |
// Un-comment the following line to test the | |
// "early-out" capability by failing on the first | |
// function call attempted. | |
//#define EARLY_OUT | |
#ifdef EARLY_OUT | |
#define FOORETDEF 1 | |
#else | |
#define FOORETDEF 0 | |
#endif | |
// The following function prototypes are each followed | |
// by a corresponding GLOBAL variable that is used | |
// to set the return value of the corresponding | |
// simulator function. | |
// 0 indicates success for the function call, | |
// any other value indicates failure. | |
// The different functions are called at different | |
// points in the control structure as described | |
// in comments to the right of each line: | |
int foo(); int fooret = FOORETDEF; // called early in the chain, light load | |
int bar(); int barret = 0; // called after foo(), heavier load | |
int baz(); int bazret = 0; // called last in the chain, light load | |
int buzz(); int buzzret = 2; // used to test correctness | |
// Main will perform the timing tests: | |
int main() | |
{ | |
int err; | |
bool stillValid = true; | |
int test_size = 1000; | |
#ifdef STRUCTURE_ONLY | |
test_size *= 5000; | |
#endif | |
int ret_val, trial_1_err, trial_2_err, trial_3_err; | |
int i; | |
clock_t start_clock, end_clock; | |
int trial_1_sum = 0; | |
int trial_2_sum = 0; | |
int trial_3_sum = 0; | |
int ntrials = 100; | |
// don't time this one... | |
// it is here just to get the program | |
// into a 'steady state' WRT the system | |
for(i = 0; i < test_size; i++){ | |
stillValid = true; | |
if ((err = foo()) != 0) | |
stillValid = false; | |
else if ((err = bar()) != 0) | |
stillValid = false; | |
else if ((err = bar()) != 0) | |
stillValid = false; | |
else if ((err = bar()) != 0) | |
stillValid = false; | |
else if ((err = baz()) != 0) | |
stillValid = false; | |
ret_val = err; | |
} | |
// BEGIN TIMED TRIALS: | |
for(int trial = 0; trial < ntrials; trial++){ | |
// Trial 1: A standard if-else chain: | |
start_clock = clock(); | |
for(i = 0; i < test_size; i++){ | |
stillValid = true; | |
if ((err = foo()) != 0) | |
stillValid = false; | |
else if ((err = bar()) != 0) | |
stillValid = false; | |
else if ((err = bar()) != 0) | |
stillValid = false; | |
else if ((err = bar()) != 0) | |
stillValid = false; | |
else if ((err = baz()) != 0) | |
stillValid = false; | |
ret_val = err; | |
} | |
end_clock = clock(); | |
trial_1_err = err; | |
trial_1_sum += end_clock - start_clock; | |
ret_val *= 2; // This just attempts to prevent the compiler from optimizing `ret_val` out. | |
// Trial 2: Single logical expression using | |
// the AND operator which short-circuits | |
start_clock = clock(); | |
for(i = 0; i < test_size; i++){ | |
stillValid = true; | |
stillValid = stillValid | |
&& (err = foo()) == 0 | |
&& (err = bar()) == 0 | |
&& (err = bar()) == 0 | |
&& (err = bar()) == 0 | |
&& (err = baz()) == 0; | |
ret_val = err; | |
} | |
end_clock = clock(); | |
trial_2_err = err; | |
trial_2_sum += end_clock - start_clock; | |
ret_val *= 2; // This just attempts to prevent the compiler from optimizing `ret_val` out. | |
// Trial 3: Original (Apple-esque) version | |
// using `goto` and a label. | |
start_clock = clock(); | |
for(i = 0; i < test_size; i++){ | |
if ((err = foo()) != 0) | |
goto fail; | |
if ((err = bar()) != 0) | |
goto fail; | |
if ((err = bar()) != 0) | |
goto fail; | |
if ((err = bar()) != 0) | |
goto fail; | |
if ((err = baz()) != 0) | |
goto fail; | |
fail: | |
ret_val = err; | |
} | |
end_clock = clock(); | |
trial_3_err = err; | |
trial_3_sum += end_clock - start_clock; | |
ret_val *= 2; // This just attempts to prevent the compiler from optimizing `ret_val` out. | |
} | |
cout << "Test `if` statement results; \n"; | |
if(trial_1_err == 0){ | |
cout << "Ended up OK.\n"; | |
} | |
else{ | |
cout << "Ended up FAILING with code " << trial_1_err << "\n"; | |
} | |
int trial_1_avg = round(static_cast<double>(trial_1_sum) / ntrials); | |
cout << "AVG TIME SPENT: " << trial_1_avg << " \"clock\" units.\n\n"; | |
cout << "Test `&&` results; \n"; | |
if(trial_2_err == 0){ | |
cout << "Ended up OK.\n"; | |
} | |
else{ | |
cout << "Ended up FAILING with code " << trial_2_err << "\n"; | |
} | |
int trial_2_avg = round(static_cast<double>(trial_2_sum) / ntrials); | |
cout << "AVG TIME SPENT: " << trial_2_avg << " \"clock\" units.\n\n"; | |
cout << "Test `goto` results; \n"; | |
if(trial_3_err == 0){ | |
cout << "Ended up OK.\n"; | |
} | |
else{ | |
cout << "Ended up FAILING with code " << trial_3_err << "\n"; | |
} | |
int trial_3_avg = round(static_cast<double>(trial_3_sum) / ntrials); | |
cout << "AVG TIME SPENT: " << trial_3_avg << " \"clock\" units.\n\n"; | |
cout << std::fixed << std::setprecision(2) << std::showpos; | |
cout << "Avg Speed ratio `if-else` VS `&&` : " << std::right << std::setw(6) << 100 * (1.0 - trial_1_avg / static_cast<double>(trial_2_avg)) << "%\n"; | |
cout << "Avg Speed ratio `goto` VS `if-else`: " << std::right << std::setw(6) << 100 * (1.0 - trial_3_avg / static_cast<double>(trial_1_avg)) << "%\n"; | |
cout << "Avg Speed ratio `goto` VS `&&` : " << std::right << std::setw(6) << 100 * (1.0 - trial_3_avg / static_cast<double>(trial_2_avg)) << "%\n"; | |
return 0; | |
} | |
// Simulator functions that can either return | |
// values directly or perform some simulated | |
// work load (depending on whether STRUCTURE_ONLY | |
// is defined above). | |
int foo() { | |
#ifdef STRUCTURE_ONLY | |
return fooret; | |
#endif | |
int z = 0; | |
for(int i = 0; i < 128; i++){ | |
z += cos(i); | |
} | |
return (z == fooret) ? z : fooret; | |
} | |
int bar() { | |
#ifdef STRUCTURE_ONLY | |
return barret; | |
#endif | |
int z = 0; | |
for(int i = 0; i < 512; i++){ | |
z += cos(i); | |
} | |
return (z == barret) ? z : barret; | |
} | |
int baz() { | |
#ifdef STRUCTURE_ONLY | |
return bazret; | |
#endif | |
int z = 0; | |
for(int i = 0; i < 128; i++){ | |
z += cos(i); | |
} | |
return (z == bazret) ? z : bazret; | |
} | |
int buzz() { | |
return buzzret; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment