The above case was real-world. It involved a loss of state information during power-cycles, and the information lost was never relevant — except, as it turns out, for a very specific class and sequence of sensor failures with intervening power-cycles; a condition that could not have been foreseen. The state it reached was not even incorrect; what was incorrect, for the class of sensor failure, was the transition — the reinstatement of the previously failed sensor.

Short of full specifications and formal methods, I’m not sure how detecting such a thing might have been automated. It does seem like an excellent topic for research, though.

With this “cocktail-shaker” approach, the functional decomposition and the primitive identification are intimately related; they are done on concert and cannot be separated. In fact, the primitives ID usually shapes the functional decomposition as it progress, and vice versa. Furthermore, both aspects of the design need to be done by very experienced and skilled people, and as few as possible of them. Brooks’ law applies with a vengeance…

A key to all of this, IMHO, is doing a comprehensive ERD as a first step; it will clarify the relationships among the data of the problem, which in turn begins to suggest the design architecture, leading to the implementation architecture. Of course, the data schema will change, but not as much as functional requirements usually do, so maintaining the ERD, once created, shouldn’t be unduly burdensome. The ERD also serves as an “anchor” as functional requirements change — sometimes a proposed requirements change will, upon being related to the ERD, be discovered to be not such a good idea, or a better way to achieve the change’s objective is discovered.

I also think that this “cocktail-shaker” approach is orthogonal to competing methodologies such as waterfall vs. Agile.

BTW, Capers Jones’s stats show that reuse is far and away the most effective approach to reducing software defects; nothing else even comes close. And I have made reuse a part of my professional practice for a very long time. I have created, and currently babysit, 1/2 million lines of C that are rife with reuse at just about every conceivable level.

In fact, IMHO identifying reusable components (resulting in run libraries and OO classes) is an inherent part of a software architect’s or engineer’s skill set. I do agree that it’s really difficult to get many enterprises to make the necessary skills investments to achieve it, which is very sad.

Seriously, we’re talking to a couple of clients about applying static code analysis to the kind of problem you describe, although yours is an inverse version, which makes it even more interesting.

I’m looking at applying a version of static analysis I call “pseudo-dynamic analysis”, which consists of writing analysis rules to follow logic paths looking for trouble. For example, that’s how we measure Cyclomatic Complexity and find dead code. It can also find things like uninitialized variables, potential buffer overflows, and “divide by 0″ types of problems. Our rules language has built-in AST navigation facilities that make this approach easy to implement.

The 100K lines of code is no problem; we routinely deal in multiples of 100K, and the analysis takes from a few minutes to a few hours, depending on circumstances.

Your inverse problem is interesting because it requires inferring a set of possible causes from the failure condition, then looking for indicators of those causes. Depending on the condition, that could be very easy or nearly impossible. Do you have a real-world failure in mind, or was it a general question?

BTW, I’ve found that Occam’s Razor is really good at that kind of slicing

My update covered the two paragraphs that immediately followed the last line of sample code. The original text of these paragraphs was as follows:

Now there are two issues that should be emphasized about the above examples. First, the copy semantics of structs exclude any array members, so the member a will not be initialized or modified in any of the examples except the first two. Second, the last example is very inefficient since, disregarding any possible optimizations, gee will first be copied to the parameter, then to the result, then to golly.

Though I am now sure that the code I was seeing is legal; given the inefficiencies of copying structures and the large number of structs being set, I believe the originators of the application I’m dealing with would have significantly improved performance by using a pass-by-reference (pointer) strategy. While I have worked with structures in countless programs, I tend not to do direct struct-to-struct assignments, preferring to use memcpy. The latter works whether the struct contains member arrays or not, so treatment can be consistent throughout and across applications.

While I am grateful for Derek Jones response, and I accept his interpretation as authoritative with respect to the intent of the standard, my own experience and articles/advice I’ve seen from other developers leads me to believe that at least some embedded compiler vendors shared my original interpretation; so I recommend that you tread carefully if you decide to use struct-to-struct copy with array members. Run a few quick tests to make sure the implementation performs as you expect it to.

As I side-note, I was very impressed with the Coccinelle tool that Mr. Jones mentioned. I am quite sure I will be able to make use of it; and perhaps I’ll give it a review here then. In the meantime, it looks amazingly useful for anyone who is maintaining or updating a large code base, either for use in review or bulk-update.

All named members of a structure are required to be copied by a
conforming implementation, including arrays.
The only places where implementations may vary is in the handling
of any padding between named members, they are not required to
copy this.
See sentence 1298.

I can see how you might connect 6.5.16.1 and footnote 42 to think
that members having an array type would not be copied. The reason
that arrays cannot be copied is that they degenerate to pointers to
their first element, loosing all ‘arrayness’ information in the process.

Unless the struct is very small it is much more efficient to pass its
address. Of course this usage requires that the called function does
not modify the contents of the struct.

As s1298 struct assignment can be more efficient than using memcpy (gcc
does do fancy things to figure out alignment of the objects passed to
memcpy). Member by member copy can be more efficient for low numbers
of members because it has no loop overhead.

If you are making lots of very similar changes to C source you might be
interested in using Coccinelle:
http://shape-of-code.coding-guidelines.com/2009/01/08/semantic-pattern-matching-coccinelle/

You are welcome to copy-and-paste this to the comment section of your blog.

–
Derek M. Jones tel: +44 (0) 1252 520 667
Knowledge Software Ltd mailto:derek@knosof.co.uk
Source code analysis http://www.knosof.co.uk

Thank you Mr. Jones for your kind and prompt response.

I do not know the standards well, so could you direct me to where in they state that the copy semantics of structs exclude any array members. This seems inherently wrong not to copy all member of the structure. It could also take a alot more instructions, depending on how many array intermixed in the structure, to do a selective copy than just copy the whole structure.

As I said, these are my interpretations of the standard. In reviewing the materials to respond to your question, I found that I had misread one section, and failed to consider the technical corrigenda. I also dug a bit deeper by looking at “The New C Standard”, by Derek M. Jones. I now believe that a more correct interpretation is that the copying of array members in structs is implementation optional.

The rule in question is not explicitly stated anywhere that I can find, and I am not entirely confident that my interpretation is correct.
Nonetheless here are the areas that lead me to this conclusion:

• Section 6.5.16.1 Makes no provision for an assignment to an array. (i.e. direct array-to-array copy is not supported).
• Footnote 42 to Section 6.2.6.1 par 6 indicates that a structure assignment may be copied via a memcpy or via element-by-element copy. If the latter is used, I would expect it to be via the rules of the previously mentioned section.
• Section 6.7.2.1, was heavily ammended by TC2. According to the new paragraph 22, which is discussing flexible array members, it indicates that the portions of the flexible array member which reside within the structure size may either be copied or overwritten by arbitrary data. While this is a specific case, the treatment seems consistent with my interpretation.

By the way, inefficient or not, the compiler implementation I am dealing with is performing the member-by-member copy of structs.

The purpose of the article was to share a powerful technique for manual static analysis. Actually I work with a number of automated analysis tools. I am very familiar with PolySpace. I have trained people in its use, and I have sold it into client sites. It was one of the static analyzers used on this code, and it did not and could not find the issue; and we could not find a modeling technique that would permit us to find it. The capabilities of the tool are a bit stronger now than they were then, but even in the best case PolySpace would have required extensive setup, code annotation, and modeling. PolySpace also had some issues in how it dealt with bitfield values and bitwise operators in C. I don’t believe that any automated analysis tool in existence could have done this job. The viable options were formal methods, simulation, and manual analysis. Formal methods suffers from fidelity issues, and simulation was done in parallel by three of the original developers using MATLAB. The simulation team also found the issue at about the same time the analysis did, but they had a two or three day head-start.

It is not true that PolySpace creates all possible test cases. It uses abstract interpretation to mathematically try all possible values for a variable value at every point in the program. In many cases it also tries values that are not possible, and values that are not possible in combination. This makes it valuable for detecting semantic errors, but without extensive modeling it generates many false positives and while it detects where exceptions might potentially be thrown; it is fairly useless for determining correct decision making in code not specifically written to take advantage of its analysis strengths. Setting up for a PolySpace analysis of a substantial program can take a great deal of time; and if I recall correctly, the run time of the PolySpace analysis on that application was actually longer than the time I took for my manual analysis; and we had to run several times as we modeled to reduce false positives. We had the fastest PolySpace server configuration available at the time.