Skip to content

Instantly share code, notes, and snippets.

@jasoncausey
Created February 27, 2014 21:48
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jasoncausey/9260279 to your computer and use it in GitHub Desktop.
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…
/**
* @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