The id Software company possesses a PVS-Studio license. However, we decided to test the source codes of Doom 3 that have been recently laid out on the Internet. The result is the following: we managed to find just few errors, but still they are there. I think it can be explained by the following fact.

A part of the Doom 3 code is still in use, and perhaps developers have fixed errors there. And another part of the code is obsolete and not used now. Most likely, the suspicious code fragments have been found in this very part.

For those who want to know more on the subject, in this article we cite code fragments the PVS-Studio analyzer gave warnings for. As usually, let me remind you that I will speak only on some of the warnings, while the other project fragments require us to know the program's structure, so I did not examine them.

The source code of Doom3 was published on GitHub and official FTP of the company under the GPL v3 license. I used the PVS-Studio 4.39 analyzer for analysis.

Fragment 1. Suspicious condition.

#define BIT( num ) ( 1 << ( num ) )
const int BUTTON_ATTACK = BIT(0);
void idTarget_WaitForButton::Think( void ) {
  ...
  if ( player &&
      ( !player->oldButtons & BUTTON_ATTACK ) &&
      ( player->usercmd.buttons & BUTTON_ATTACK ) ) {
  ...
}

PVS-Studio diagnostic message: V564 The '&' operator is applied to bool type value. You've probably forgotten to include parentheses or intended to use the '&&' operator. Game target.cpp 257

Note the fragment "!player->oldButtons & BUTTON_ATTACK". The developers intended to check here that the least significant bit is equal to 0. But the priority of the '!' operator is higher than that of the '&' operator. It means that the condition works according to the following algorithm:

(!player->oldButtons) & 1

It turns out that the condition is true only when all the bits equal zero. This is the correct code:

if ( player &&
    ( ! ( player->oldButtons & BUTTON_ATTACK ) ) &&
    ( player->usercmd.buttons & BUTTON_ATTACK ) ) {

Fragment 2. Suspicious loop.

void idSurface_Polytope::FromPlanes(...)
{
  ...
  for ( j = 0; j < w.GetNumPoints(); j++ ) {
    for ( k = 0; k < verts.Num(); j++ ) {
      if ( verts[k].xyz.Compare(w[j].ToVec3(),
                                POLYTOPE_VERTEX_EPSILON ) ) {
        break;
      }
    }
    ...
  }
  ...
}

PVS-Studio diagnostic message: V533 It is likely that a wrong variable is being incremented inside the 'for' operator. Consider reviewing 'j'. idLib surface_polytope.cpp 65

The nested loop increments the 'j' variable instead of 'k'. The 'k' variable is not incremented at all. Results of such a loop cannot be predicted. This is the correct code:

for ( k = 0; k < verts.Num(); k++ ) {

Fragment 3. One more suspicious loop.

bool idMatX::IsOrthonormal( const float epsilon ) const {
  ...
  for ( int i = 0; i < numRows; i++ ) {
    ...
    for ( i = 1; i < numRows; i++ ) {
      ...
    }
    if ( idMath::Fabs( sum ) > epsilon ) {
      return false;
    }
  }
  return true;
}

PVS-Studio diagnostic message: V535 The variable 'i' is being used for this loop and for the outer loop. idLib matrix.cpp 3128

One and the same variable is used to arrange both the outer loop and the nested loop. The both loops have the same loop end condition: i < numRows. It turns out that the outer loop always performs only one iteration. To fix the code you may use another variable in the nested loop.

Fragment 4. Undefined behavior.

int idFileSystemLocal::ListOSFiles(...)
{
  ...
  dir_cache_index = (++dir_cache_index) % MAX_CACHED_DIRS;
  ...
}

PVS-Studio diagnostic message: V567 Undefined behavior. The 'dir_cache_index' variable is modified while being used twice between sequence points. TypeInfo filesystem.cpp 1877

The "dir_cache_index" variable is changed twice in one sequence point. It does not matter that the prefix increment is used and, theoretically, nothing prevents the compiler from creating the following code:

A = dir_cache_index;
A = A + 1;
B = A % MAX_CACHED_DIRS;
dir_cache_index = B;
dir_cache_index = A;

Of course, the expression is most likely calculated as it should be. But you cannot be absolutely sure because the result is determined by the type and version of the compiler as well as optimization settings. This is the correct code:

dir_cache_index = (dir_cache_index + 1) % MAX_CACHED_DIRS;

Fragment 5. Suspicious array clearing.

void idMegaTexture::GenerateMegaMipMaps() {
  ...
  byte *newBlock = (byte *)_alloca( tileSize );
  ...
  memset( newBlock, 0, sizeof( newBlock ) );
  ...
}

PVS-Studio diagnostic message: V579 The memset function receives the pointer and its size as arguments. It is possibly a mistake. Inspect the third argument. DoomDLL megatexture.cpp 542

Only part of the 'newBlock' array is filled with nulls. Most likely, it is an incorrect situation. It seems to me that this fragment looked like this earlier:

byte newBlock[ CONST_ARRAY_SIZE ];
...
memset( newBlock, 0, sizeof( newBlock ) );

Then the requirements changed and the size of the 'newBlock' array started to change too, but the programmers forgot about the function clearing it. This is the correct code:

memset( newBlock, 0, tileSize );

Fragment 6. One more instance of suspicious array clearing.

void Sys_GetCurrentMemoryStatus( sysMemoryStats_t &stats ) {
  ...
  memset( &statex, sizeof( statex ), 0 );
  ...
}

PVS-Studio diagnostic message: V575 The 'memset' function processes '0' elements. Inspect the third argument. DoomDLL win_shared.cpp 177

Arguments are mixed up when calling the 'memset' function. The function clears 0 bytes. By the way, this error is rather widely-spread. I came across it in many projects.

This is the correct function call:

memset( &statex, 0, sizeof( statex ) );

Fragment 7. Hello, Copy-Paste.

void idAASFileLocal::DeleteClusters( void ) {
  ...
  memset( &portal, 0, sizeof( portal ) );
  portals.Append( portal );

  memset( &cluster, 0, sizeof( portal ) );
  clusters.Append( cluster );
}

PVS-Studio diagnostic message: V512 A call of the 'memset' function will lead to underflow of the buffer '& cluster'. DoomDLL aasfile.cpp 1312

Note the similarity between the two upper and the two lower code lines. The last two lines must have been written through Copy-Paste. This is the thing that caused the error here. The programmer forgot to replace the word 'portal' with the word 'cluster' in one place. As a result, only a part of the structure is cleared. This is the correct code:

memset( &cluster, 0, sizeof( cluster ) );

There were some other incompletely cleared arrays in the code, but they are not of much interest.

Fragment 8. Suspicious pointer handling.

void idBrushBSP::FloodThroughPortals_r(idBrushBSPNode *node, ...)
{
  ...
  if ( node->occupied ) {
    common->Error( "FloodThroughPortals_r: node already occupied\n" );
  }
  if ( !node ) {
    common->Error( "FloodThroughPortals_r: NULL node\n" );
  }
  ...
}

PVS-Studio diagnostic message: V595 The 'node' pointer was utilized before it was verified against nullptr. Check lines: 1421, 1424. DoomDLL brushbsp.cpp 1421

The 'node' pointer is dereferenced first: node->occupied. And then it is suddenly checked if it is not equal to NULL. This is a very suspicious code. I do not know how to fix it because I do not know the logic of the function operation. Perhaps it is just enough to write it that way:

if ( node && node->occupied ) {

Fragment 9. Suspicious string format.

struct gameVersion_s {
  gameVersion_s( void )
  {
    sprintf(string, "%s.%d%s %s %s",
            ENGINE_VERSION, BUILD_NUMBER, BUILD_DEBUG,
            BUILD_STRING, __DATE__, __TIME__ );
  }
  char string[256];
} gameVersion;

PVS-Studio diagnostic message: V576 Incorrect format. A different number of actual arguments is expected while calling 'sprintf' function. Expected: 7. Present: 8. Game syscvar.cpp 54

What is suspicious about this is that the '__TIME__' argument is not used in any way.

Fragment 10. Confusing code.

There are several code fragments which seem to work properly but look strange. I will cite only one example of this code.

static bool R_ClipLineToLight(..., const idPlane frustum[4], ...)
{
  ...
  for ( j = 0 ; j < 6 ; j++ ) {
    d1 = frustum[j].Distance( p1 );
    d2 = frustum[j].Distance( p2 );
    ...
  }
  ...
}

As a tip, the programmer has written that the 'frustum' array consists of 4 items. But there are 6 items being processed. If you look at the 'R_ClipLineToLight' call, the array there consists of 6 items. That is, everything must work as intended but the code makes you feel uneasy about it.

What other errors and defects are concerned, you can see them launching the PVS-Studio analyzer. By the way, taking the opportunity, I want to give my best regards to John Carmack and tell him that we will soon fix the flaw that does not allow the id Software company to use PVS-Studio at full.

This flaw is the analyzer's low operation speed. Taking into account the large size of the source code the company deals with, this is a crucial limitation. In PVS-Studio 4.50 that will be released in this year, you will be able to use Clang as a preprocessor instead of the Visual C++ preprocessor. This will provide a significant speed-up of project analysis. For example, the Doom 3 source codes are checked within 26 minutes when using the Visual C++ preprocessor. With the Clang preprocessor, it will be 16 minutes. Well, this example is not very good because the analysis speed boost will be much more significant for most other projects.

But for now you will have to use the Visual C++ preprocessor by default - Clang still has some issues of incompatibility and defects concerning the Windows-platform. So, only 80% of projects are checked successfully with the new preprocessor.

The third myth is: "Dynamic analysis performed by tools like valgrind for C/C++ is much better than static code analysis".

The statement is rather strange. Dynamic and static analyses are just two different methodologies which supplement each other. Programmers seem to understand it, but I hear it again and again that dynamic analysis is better than static analysis.

Let me list advantages of static code analysis.

Diagnostics of all the branches in a program

Dynamic analysis in practice cannot cover all the branches of a program. After these words, fans of valgrind tell me that one should create appropriate tests. They are right in theory. But anyone who tried to create them understands how complicated and long it is. In practice, even good tests cover not more than 80% of program code.

It is especially noticeable in code fragments handling non-standard/emergency situations. If you take an old project and check it with a static analyzer, most errors will be detected in these very places. The reason is that even if the project is old, these fragments stay almost untested. Here is a brief example to show you what I mean (FCE Ultra project):

fp = fopen(name,"wb");
int x = 0;
if (!fp)
  int x = 1;

The 'x' flag will not be equal to one if the file wasn't opened. It is because of such errors that something goes wrong in programs: they crash or generate meaningless messages instead of adequate error messages.

Scalability

To be able to check large projects through dynamic methods regularly, you have to create a special infrastructure. You need special tests. You need to launch several instances of an application in parallel with different input data.

Static analysis is scaled several times easier. Usually you need only a multi-core computer to run a tool performing static analysis.

Analysis at a higher level

One of the advantages of dynamic analysis is that it knows what function and with what arguments is being called. Consequently, it can check if the call is correct. Static analysis can't know it and can't check arguments' values in most cases. This is a disadvantage of this method. But static analysis performs analysis at a higher level than dynamic analysis. This feature allows a static analyzer to detect issues which are correct from the viewpoint of dynamic analysis. Here is a simple example (ReactOS project):

void Mapdesc::identify( REAL dest[MAXCOORDS][MAXCOORDS] )
{
  memset( dest, 0, sizeof( dest ) );
  for( int i=0; i != hcoords; i++ )
    dest[i][i] = 1.0;
}

Everything is good here from the viewpoint of dynamic analysis, while static analysis gives the alarm because it is very suspicious that the number of bytes being cleared in an array coincides with the number of bytes the pointer consists of.

Here you are another example from the Clang project:

MapTy PerPtrTopDown;
MapTy PerPtrBottomUp;
void clearBottomUpPointers() {
  PerPtrTopDown.clear();
}
void clearTopDownPointers() {
  PerPtrTopDown.clear();
}

Is there anything here dynamic analysis may find suspicious? Nothing. But a static analyzer can suspect there is something wrong. The error is this: inside clearBottomUpPointers() there must be this code: "PerPtrBottomUp.clear();".

The fourth myth is: "A static analyzer must enable users to add user-made rules. Programmers want to add their own rules."

No, they don't. They actually want to solve some tasks of searching for particular language constructs. It is not the same thing as creating diagnostic rules.

I have always answered that implementation of own rules is not the thing programmers actually want. And I never saw any other alternative than implementing diagnostic rules by the analyzer's developers at the request of programmers (an article on the subject). I have had a fruitful conversation with Dmitry Petunin recently. He is the director of an Intel department of compiler testing and software verification tool development. He enlarged my understanding of this subject and voiced the idea I had been pondering over but failed to give the final formulation of.

Dmitry confirmed my belief that programmers wouldn't write diagnostic rules. The reason is very simple - it is very hard. Some static analysis tools enable users to extend the rule set. But it is done rather as a pure formality or for convenience of the tool's developers themselves. You need to know the subject very deeply to be able to develop new diagnostic rules. If an enthusiast without skill starts creating them, they will be of little use.

My understanding of the issue was over at this point. Dmitry, being more skilled than I, helped me learn more. In brief, this is how the situation looks.

Indeed, programmers want to be able to search for some particular patterns/errors in their code. They really need it. For example, someone needs to find all the explicit conversions of the int type to float. This task cannot be solved by such tools as grep, since it is unknown what type the FOO() function will return in a "float(P->FOO())" -like construct. At this moment the programmer comes to the idea that he/she can implement search of such constructs by adding his/her own check into the static analyzer.

This is where the key point lies. The programmer does not need to create his/her analysis rules. He/she needs to solve a particular issue. What he/she wants is a very small task from the viewpoint of static analysis mechanisms. It is like using a car to light cigarettes with its cigarette lighter.

That's why both Dmitry and I don't support the idea of providing users with API to handle the analyzer. It is an extremely difficult task from the viewpoint of development. Besides, people will hardly use more than 1% of it. So, it's irrational. It is easier and cheaper for a developer to implement users' wishes than create a complex API for add-ons or a special language of rule description.

The readers may say: "then make only 1% of the functionality in API available, and everyone will be happy". Yes, right. But look where the emphasis has moved: from developing own rules we have come to the idea that we just need a tool similar to grep but possessing some additional information about program code.

There is no such a tool yet. If you want to solve some task, write to me, and we will try to implement it in the PVS-Studio analyzer. For example, we have recently implemented several requests on searching for explicit type conversions: V2003, V2004, V2005. It is much easier for us to implement such wishes than create and maintain an open interface. It's also easier for users themselves.

By the way, such a tool might appear some time later within the scope of Intel C++. Dmitry Petunin said they had discussed a probability of creating a grep-like tool possessing knowledge about code structure and variable types. But it was discussed just in theory. I don't know whether or not they really intend to create this tool.

The fifth myth: "You can easily evaluate capabilities of a static analyzer on a small test code".

This is how this statement looks in discussions on forums (this is a collective image):

I've written a special program, its size is 100 code lines. But the analyzer doesn't generate anything although all the warning levels are enabled. This [tool of yours] / [static analysis] in general is just rubbish.

It is not the static analysis methodology which is rubbish, but this approach to evaluating the usability of a particular tool. The incorrectness of this kind of tool studying consists of two aspects:

1.

Programmers think they don't make simple mistakes. This phenomenon was discussed in Myth 2. So they try to feed an analyzer with a tricky sample and feel happy secretly when the analyzer can't find the error. This game is interesting yet senseless.

You should understand that most errors are simple as hell, and static analyzers detect them very well. The paradox is that it's much more difficult to invent a simple mistake than a complicated one. Here you are an example. Can you ever guess to write a sample like this?

int threadcounts[] = { 1, kNumThreads };
for (size_t i = 0;
     i < sizeof(threadcounts) / sizeof(threadcounts); i++) {

I doubt. I cannot imagine one can make such a silly mistake and write "sizeof(threadcounts) / sizeof(threadcounts)". So, such an example will never be created on purpose. By the way, this fragment is taken not from a student's lab work, but from the Chromium project. It is diagnosed by the PVS-Studio analyzer very easily, of course.

2.

Written samples are of random character, and they are few. So you may get very different results depending on chance. You may invent 5 errors that will be successfully found by one analyzer and not found by another analyzer. Or you may create a program with five errors, and two analyzers will give opposite results for it. The sampling for such an investigation is too small. To be able to compare and study tools with at least somewhat reliable results, you must write a program text with at least 500 different errors. An investigation based on 5-10 errors is not reliable.

Moreover, programmers expect to see diagnostic messages on errors of some particular type and forget about the rest. For example, almost all the programmers write one and the same sample with a memory release defect:

void Foo()
{
  int *a = (int *)malloc(X);
  int *b = (int *)malloc(Y);
  //...
  free(a);
}

Some analyzers detect this error, the others don't. For instance, PVS-Studio does not diagnose memory leaks currently. But it can find the following stuff:

static int rr_cmp(uchar *a,uchar *b)
{
  if (a[0] != b[0])
    return (int) a[0] - (int) b[0];
  if (a[1] != b[1])
    return (int) a[1] - (int) b[1];
  if (a[2] != b[2])
    return (int) a[2] - (int) b[2];
  if (a[3] != b[3])
    return (int) a[3] - (int) b[3];
  if (a[4] != b[4])
    return (int) a[4] - (int) b[4];
  if (a[5] != b[5])
    return (int) a[1] - (int) b[5];
  if (a[6] != b[6])
    return (int) a[6] - (int) b[6];
  return (int) a[7] - (int) b[7];
}

There must be "return (int) a[5] - (int) b[5];" instead of "return (int) a[1] - (int) b[5];".

Why does nobody write such examples? Note that PVS-Studio has found this error in the MySQL project.

The conclusion is, adequate investigation or comparison of tools can be carried out only with real projects. You take project A, test it with PC-Lint / Visual C++ / PVS-Studio / C++Test, study all the messages attentively, draw up a table of results (how many and which errors each analyzer has found). This is the only real investigation and comparison. For example: "Comparing the general static analysis in Visual Studio 2010 and PVS-Studio by examples of errors detected in five open source projects ".

However, you don't necessarily need to fight for the first prize in competitions to attract Intel's attention; there are other interesting and useful ways too. For example, you can become a participant of the Intel Software Network (ISN) community and automatically become a participant in the "Black Belt Software Developer" contest. It is this program that I wanted to tell you about.

Intel Software Network is a community of software developers. It includes blogs and articles by the community members or Intel company's employees, forums, announcements of new events, contests and so on. What is important and interesting is that you can ask questions directly of Intel workers in forums or in article comments. Or you may give answers yourself, publish interesting content, etc., i.e. be an active and useful community member. It is this what Intel takes into account when selecting candidates to nominate for the "Intel Black Belt Software Developer" award.

This is how the Intel site defines a person deserving to bear this title:

This is a title for community members who demonstrate outstanding expertise on Intel technologies and enrich our communities by regularly sharing their knowledge and expertise, providing help & support in the discussion forums, submitting content such as articles and participating in the communities. It is recognition of the community leadership and contribution by these members.

While you are on your way to perfection, you will be given belts of different colors. To learn more about this program, its conditions and advantages see the following posts:

• Intel® Black Belt Software Developer;
• Intel Brown Belt Software Developer and Intel Green Belt Software Developer - FAQs;
• Intel® Black Belt Software Developers - FAQs;
• Intel® Black Belt Software Developer Terms and Conditions.

And what myself is concerned, I'm writing this post from joy and gratitude. The reason is that I have been given the Intel Black Belt Software Developer title. I was very pleased to receive congratulations at the ISN-meeting and get a wonderful high-performance laptop as a prize.

The prize is a Sony VAIO Intel Core i7-based laptop with 4 cores, 6 Gbytes of memory, a Blu-ray driver and other bonuses. There are other presents besides this one and even more advantages provided by the title. For example, I've become a user of the Intel Parallel Studio XE 2011 software.

What do you need to get appreciated? Nothing extraordinary. You should be an active community member, write articles and keep in touch with people. I, for instance, even did not think about and reckon for the Black Belt title. To be honest, I was more concerned with the discussions of PVS-Studio. That's why it was very unexpectedly and pleasant to get the award for interesting articles and contribution into the ISN community's life.

Thanks to everyone. I will try to continue pleasing my readers with interesting posts and unicorns.

A wide variety of ways exist for addressing these kinds of security challenges and Intel offers technologies to assist in the battle.  For probably the most sane and scalable way of addressing security issues, at least for enterprise applications, I would recommend that you jump over to Blake Dournaee's (Intel) blogs "Using a Service Gateway to Protect against the OWASP Top 10" and "How about a Security Layer?".  The idea of a Security Layer on a Service Gateway is truly the most comprehensive way to tackle these kinds security issues. 

Never-the-less, some enterprise shops may be unwilling to re-architect their legacy systems using the security layer approach and some developers are targeting client applications.  What tools and techniques can these developers use to mitigate security bugs?  For those developers I offer the following:

 I had a chat with Julian Horn, who is Intel's architect on the compiler team for the Static Security Analysis (SSA) tool.  SSA comes as part of the Intel compiler (C/C++/Fortran) and is available for Linux* and Windows*.  SSA identifies various coding errors such as memory and resource leaks, pointer and array errors, incorrect use of OpenMP* directives, and incorrect use of Cilk Plus language features.  SSA also identifies security errors such as buffer overflows and boundary violations, use of uninitialized variables and objects, incorrect usage of pointers and dynamically allocated memory, dangerous use of unchecked input, arithmetic overflow and divide by zero, and misuse of string, memory, and formatting library routines.

I was curious what kind of security flaws that SSA could find. Specifically, I wanted to know if it could help developers to mitigate any of the most dangerous software errors as identified by the Common Weakness Enumeration (CWE) community sponsored by Mitre.

After an email exchange with Julian, and pouring over the descriptions of the top twenty-five security bugs as reported by CWE, I determined that the Intel SSA could help to mitigate at least two of the top five errors listed.  Coming in at error number two is "OS Command Injection", and at number three was "Classic Buffer Overflow". How can SSA mitigate these errors?

Identification and Mitigation of CWE Top Error #2 (OS Command Injection)
OS Command Injection is an error type that really should be checked on both server and client side applications.  The essence of this error, or potential attack, is that, sometimes, your application is a bridge linking an outsider to the internals of your operating system. If your application simply passes un-trusted inputs to be fed into a command string that you pass to a system call, then your application can inadvertently wreak all kinds of havoc on the system. The recommended mitigation step is to validate all inputs to your application.

A simple minded BAD example, in "C", might be issuing a system call to delete a file that a user types in.

          // user inputs a filename to be deleted
          scanf (“%s”, str);                        // buffer overflow
          sprintf (cmd, "del %s", str);   // another buffer overflow
          system(cmd);                             // OS command injection, due to not validating the input

What happens if the user types into the input *.* rather than a normal filename?  Since the input has not been validated and was passed right to the OS, then clearly deletions unintended by the developer would occur. 

Analyzing your code for un-validated input is known as taint analysis – tainted input means un-validated input.  CWE recommends doing a taint analysis to identify where in your code you are not validating input, and then take steps to remove the taint.

Intel's Static Security Analysis tool uses a taint analysis algorithm to detect whether or not an unknown input has been compared against another value.  There are various rules under which taintedness is propagated from one variable to another.  One rule is that when a value is compared against another value this removes the taint.  If an untested value is used in a “dangerous” context, then you get an error reported by SSA.

The logic here is that a comparison is considered sufficient to sanitize the value.  The example below demonstrates the idea of tainted variable, x.  When x is used blindly with no comparisons done on it to check it validity, SSA flags this value as tainted:

          x = input;
          a[x] = 0;   // SSA identifies use of tainted value x

The example below uses a comparison operator to check the input value x, so it is considered untainted now by SSA:

          x = input;
          ok = (x < 10);     // comparison un-taints the value x
          if (ok) a[x] = 0;

This "good" example might still have some issues with it, the checking is not extensive, but at least the developer went to some effort to validate the input.

The key take away here is to use tools to find un-validated inputs and then add the necessary validation around each of these inputs.

Identification and Mitigation of CWE Top Error #3 (Classic Buffer Overflow)
Michael Howard & David LeBlanc, in their book Writing Secure Code, 2nd edition, identify the buffer overflow (AKA buffer overrun) as public enemy number one.  The Common Weakness Enumeration list is kinder, listing this issue as the number three most dangerous error.  It is well known that certain "C" functions are unsafe because they are vulnerable to buffer overflow attacks. These functions should be replaced with safe counterparts : strcpy, strncpy, strcat, and gets, among others. 

The buffer overflow terminology comes from the idea that if you continue to pour water into a finite sized container, the container will eventually overflow. In computer terms, the analogy means that copying too much text into a finite sized array, will cause the extra text in the buffer to spill over into areas of memory that the developer did not intend.  These areas of memory get corrupted with the excess text and malicious coders use this to exploit your application and potentially run malicious code within the confines of your application's process. I found the following buffer overflow example insightful, though I didn't want to copy it here in its entirety and will simply link to it instead.  It demonstrates how an overflow attack can occur and is found on an MSDN blog by Robert Horvick.

Other strains of buffer overflow can occur in some types of formatted input.  The biggest issue here is when the "%s" input format is used. This format specifier is generally regarded as unsafe. In the Intel Parallel Studio XE evaluation guide on Static Security Analysis (SSA), there is a nice example of SSA detecting a buffer overflow in a fscanf function. In this case, SSA indicates that it found an "unsafe format specifier," which is essentially a condition that can lead to buffer overflow.  The code snippet from this guide is as follows:

          // example that would allow buffer overflow  
          char data[255];
          fscanf(dfile, "%s", data);
          if (strcmp(data, string) != 0) {
                fprintf(stderr, "parse: Expected %s, got %s \n", string, data);
          }

The call to fscanf uses an input descriptor string with a “%s” format specifier. This reads input characters up to the next newline and stores the data in the array “data”. There is no guarantee that the number of characters read will not overflow the bounds of the array, so this statement could corrupt memory.  SSA reported this as an error and the developer should follow up by making code changes using an alternative format specifier such as the "%255s"  to limit the number of characters read in.  The corrected code should be something like this:

          // example that corrects the undesired  buffer overflow  condition
          char data[255];
          fscanf(dfile, "%255s", data);
          if (strcmp(data, string) != 0) {
                fprintf(stderr, "parse: Expected %s, got %s \n", string, data);

For similar tips on how to protect your code through defensive programming, read this article by McGraw & Viega, Make your software behave: Preventing buffer overflows.

The key take away here, in addition to validating all  inputs, is to find unsafe “C” functions and format specifiers, and replace them with safe alternatives .

What should a developer do?
The security bugs discussed above are two of the most dangerous and prevalent according to CWE.  These bugs affect client applications that are run on laptops, desktops, ultrabooks, as well as enterprise applications on web servers, application servers, database servers and more.  Developers are urged to find these kinds of bugs using tools such as Intel Static Security Analysis, and then make it a practice to validate all inputs and to replace unsafe functions (strcpy, strncpy, strcat, and gets, among others)  with safe counterparts.  To learn more about steps you can take as a developer to reduce your exposure to security attacks go to the Department of Homeland Security's Build Security In website or visit the Common Weakness Evaluation site.

Oh, and did I mention that enterprise developers  should  jump over to Blake Dournaee's (Intel) blogs "Using a Service Gateway to Protect against the OWASP Top 10" and "How about a Security Layer?" to learn an even better way to secure your systems?

For more complete information about compiler optimizations, see our Optimization Notice.

Bob Duffy & Gunjan Rawal host this extra-long episode of the AppUp show and cover some of the cool technologies, demos and announcements from Intel while at CES 2012. In this on location episode you will get a CES keynote wrap-up, overview of Ultrabooks, a sneak peak at the new Intel powered smartphone, reaction and insight from tech bloggers, and a demo of the Ultrabook optimized MixMan Spin Control app, now available on the Intel AppUp center. So enjoy this 25 minute AppUp slice of CES 2012

read more

In my blog “Transactional Synchronization in Haswell,” I describe new instructions (Intel TSX) that will improve the performance of coarse-grained locks.  Understanding coarse-grained locks and the concept of transactions are both key to understanding why Intel TSX matters.

Intel TSX may enhance performance of mutual exclusion other than simple coarse-grained locks, but I will focus on coarse-grained locking because it is common and Intel TSX allows highly concurrent accesses using only a simple locking mechanism.

An example

To motivate by illustration, let’s consider a simple hash table. Hash tables are used to map a key to a key and value pair in linear time. Two key operations are add (insert) and lookup (retrieve). Resizing and deletion are two additional operations of general interest also, but I will leave them for another time.

Designing a highly concurrent hash table is a non-trivial task, and there are many approaches to allow high levels of concurrency.  All these approach add complexity to the program, and often to the data structures themselves.

The simplest approach is a single lock approach. In such an approach, every operation on the hash table starts by obtaining the lock for the table and concludes by releasing the lock. While the lock is held for the operation, no other task on the system can obtain the lock and therefore no hash table operation is allowed to proceed.

Considering Figure 1, no concurrent operations are allowed, so each of the five operations shown would occur one at a time.

Figure 1: Five hash table operations requested

Solutions

A common solution is to break the hash table into smaller regions, and have locks that apply to regions. While this can reduce contention, it still can create needless delays and it definitely complicates the coding and the data structure.

Such an approach is a prime example of taking a coarse-grained lock (a single lock for the entire hash table) and working to make it a finer grained lock (multiple locks for smaller table sections). Coarse-grained locks are easier to use, easier to understand and easier to debug.  The only disadvantage is that they tend to impede performance in a multithreaded environment. Multicore processors are increasing the likelihood of this being a problem, and help motivate new hardware assistance so that programming has a chance to stay simple more often than without assistance.

Transactional Synchronization (Intel TSX) as a solution

What would be ideal, is to use the single lock (coarse-grained locking) because it is easy and not very error prone, but still have the performance of a fine-grained implementation. In our Figure 1 example, only one operation conflicts with another. This example does have more conflicts that would be expected in a real world example.

Considering this example, three of the operations have no collision with the other operation so the use of HLE (part of Intel TSX) on the single lock will completely elide the lock. In other words, the performance is very close to the performance of the code if no locking or unlocking code was present. The key however is that the operations are protected by the Intel TSX hardware, which has silently ensured that the protection intended by the lock is indeed assured.

The two operations that map to the same hash table entry will need to be staggered. This will occur even if we are unlucky enough to have them happen at the same time. In such a case, the Intel TSX will detect that the lock was indeed needed and some locking overhead will be incurred. What would actually happen in such a case, is that the colliding tasks will proceed into the protected code until the processor detects the conflict. As such a point, both updates will abort their protected code (also called the transaction). The most common solution then is to have each task proceed but actually enforce the lock on the second try. This means that one task will win, and delay the other, until the operation is complete. The precise decision on how to handle the collision is either up to the processor implementation with HLE, or the programmer with RTM. The processor implementation for HLE will also be fairly simple and conservative, in order to preserve the semantics of the original lock and hence compatibility with processors that lack Intel TSX.

Summary

For a hash map, Intel TSX allows for the right things to occur without losing the protection that the locks need to give. Intel TSX ensures the same results as the coarse-grained lock guarantees, but allows unrelated operations to proceed without delays that the coarse-grained locks would have caused. For more information on Transactional Synchronization, see my blog on Intel TSX.

Please check out the specification and stay tuned for information about supporting tools from Intel and others in the coming months.

In this blog, I’ll introduce Intel TSX and provide a little background. Please refer to The Transactional Synchronization Extensions Chapter (Chapter 8) in the manual for additional information. These new synchronization extensions (Intel TSX) are useful in shared-memory multithreaded applications that employ lock-based synchronization mechanisms.

In a nutshell, Intel TSX provides a set of instruction set extensions that allow programmers to specify regions of code for transactional synchronization. Programmers can use these extensions to achieve the performance of fine-grain locking while actually programming using coarse-grain locks. I have written a simple illustrative example in my blog “Coarse-grained locks and Transactional Synchronization explained.”

Locks are a low-level programming construct (close to the hardware), so any discussion of Intel TSX will be low level too. How Intel TSX might affect higher-level programming methods, or enable new programming models, is beyond the scope of my blog but I will briefly comment on it at the end of this blog.

Why is this useful?

With transactional synchronization, the hardware can determine dynamically whether threads need to serialize through lock-protected critical sections, and perform serialization only when required. This lets the processor expose and exploit concurrency that would otherwise be hidden due to dynamically unnecessary synchronization.

At the lowest level with Intel TSX, programmer-specified code regions (also referred to as transactional regions) are executed transactionally. If the transactional execution completes successfully, then all memory operations performed within the transactional region will appear to have occurred instantaneously when viewed from other logical processors. A processor makes architectural updates performed within the region visible to other logical processors only on a successful commit, a process referred to as an atomic commit.

These extensions can help achieve the performance of fine-grain locking while using coarser grain locks. These extensions can also allow locks around critical sections while avoiding unnecessary serializations. If multiple threads execute critical sections protected by the same lock but they do not perform any conflicting operations on each other’s data, then the threads can execute concurrently and without serialization. Even though the software uses lock acquisition operations on a common lock, the hardware is allowed to recognize this, elide the lock, and execute the critical sections on the two threads without requiring any communication through the lock if such communication was dynamically unnecessary.

Intel TSX Interfaces

Intel TSX provides two software interfaces. The first, called Hardware Lock Elision (HLE) is a legacy compatible instruction set extension (comprised of the XACQUIRE and XRELEASE prefixes) that are used to specify transactional regions. HLE is compatible with the conventional lock-based programming model. Software written using the HLE hints can run on both legacy hardware without TSX and new hardware with TSX. The second, called Restricted Transactional Memory (RTM) is a new instruction set interface (comprised of the XBEGIN, XEND, and XABORT instructions) that allows programmers to define transactional regions in a more flexible manner than is possible with HLE. Unlike the HLE extensions, but just like most new instruction set extensions, the RTM instructions will generate an undefined instruction exception (#UD) on older processors that do not support RTM. RTM also requires the programmer to provide an alternate code path for when the transactional execution is not successful.

In summary: “Intel Transactional Synchronization Extensions (Intel TSX) comes in two flavors: HLE and RTM. Hardware Lock Elision (HLE) is legacy compatible. Restricted Transactional Memory (RTM) offers flexibility but requires the programmer to provide an alternative code path for when transactional execution is not successful.”

The specification describes these extensions in detail and outlines various programming considerations to get the most out of them.

Intel TSX Applicability

Intel TSX targets a certain class of shared-memory multi-threaded applications; specifically multi-threaded applications that actively share data. Intel TSX is about allowing programs to achieve fine-grain lock performance without requiring the complexity of reasoning about fine-grain locking.

However, if there is high data contention the algorithm would need to change in order to have an opportunity for high scalability. There are no magic bullets that can solve the problem, since true high data contention implies that the algorithm is effectively serialized.

Transactional Programming?

How Intel TSX might affect higher-level programming methods, or enable new programming models, is beyond the scope of my blog. Several experimental compiler implementations, not related specifically to Intel TSX, are available including gcc 4.7 which will have an experimental implementation. We can expect languages standards committees will be reviewing proposals on how to add transactional models at a language level (Intel has supported the creation of the Draft Specification of Transaction Language Constructs for C++). Intel TSX may enable a more efficient implementation of some transactional models than without Intel TSX. Much work remains to focus on real-world examples of usages and applications to develop and refine future usage. Good luck to all involved!

While Intel TSX may enable efficient implementations of new programming models, it does not require a new programming model and does not propose a new programming model. Intel TSX provides hardware-supported transactional-execution extensions to ease the development and improve the performance of existing programming models.

Summary

Intel TSX provides extensions that allow programmers to specify regions of code for transactional execution. Programmers can use these extensions to achieve higher performance with lesser effort, for example achieve fine-grain locking performance while programming with coarser-grain locks. This is a big help and therefore big news for programmers.

Please check out the specification and stay tuned for information about supporting tools from Intel and others in the coming months.

What seemed most disturbing to me was the limit on the number of cores being self-inflicted. Surely we can't have reached the maximum number of cores that are possible to squeeze onto a chip? The whole "right turn" idea to add cores rather than try to cool processors reaching rocket engine temperatures was less than 10 years ago. I'm not sure where the physics starts to overshadow Moore's Law, but I thought I'd  heard that a few more generations of smaller wire sizes in processor dies were still possible. So why not push more and more cores into the same package?

It might be that the average server application (and, perhaps even more so, consumer applications) can't scale well beyond some fixed number of cores. How many cores does it take to type and post a tweet or update your Facebook status or to watch a streaming video? Would any of those tasks be faster or somehow enhanced if there were twice the number of cores available?

If we stop increasing the core counts in the next 5 years, how will new chips keep fulfilling the ever-growing hunger for more performance by consumers? Maybe it won't be about faster and faster application exeuction, but more about less energy consumption while maintaining a level of performance. I guess at some point we'll stop being concerned about Gigahertz or core counts because all processors will be able to do many of the same tasks in about the same amount of time.

I do know that power consumption is going to be a major driving design force as HPC moves closer toward Exascale platforms.  Thus, if the THX-1138 processor draws power twice as fast as the CFM602 processor, I would be more likely to build my system equipped with the former.

read more

read more

read more

read more