DEV Community: J. Marchán

Should input parameters be checked?

J. Marchán — Mon, 30 Mar 2020 15:55:49 +0000

The problem

In the last few months, I have been struggling with this problem: Should input parameters be checked? Hundreds of warnings were thrown by static analysis tool in a large base code, most of them regarding pointers which could be null or variables which could index an array outside its bounds. In order to certificate the software, those warnings must be removed. Quickly, the whole team started to code checks in every problematic variable. We were falling into a trap and the code quality started going downhill. Nobody had a magic answer (because there isn’t) and there was no time to do a deep analysis.

Suddenly, a lot of questions arose: Should the input data be validated? Should it be the caller? Should be the function called? Without noticing, these questions lead to another highly related topic: How much redundancy and robustness should software have? The very first question can not be answered if the last one has not been discussed, which is, indeed, the real question.

Fortunately, there are people who have faced this problem before. I strongly encourage to read the references. Here there are some few key points:

Searching an answer

The problem and the solution have to be present in the first stages of the software design and every member of the team should be aware of it. What is more, it is not even a technical question, it is a business one. It is different whether your software can fail and reboot or if it is not an option. It is different whether your software has a hard time restrictions or if it does not matter if it takes 5 ms more. It is different if you are writing an API or safety-critical piece of code. In other words: It is a requirements thing.

If a clear decision is not taken and the decision is left to the programmers as they go, errors will be checked on the same parameter three or four levels into the call stack and the solution implemented through the application won’t be coherent and will become crappy.

So then, how to check input data? So far, we can talk about two approaches.

Design by Contract (DBC)

A concept developed by Bertrand Meyer as a design technique “that focuses on documenting and agreeing to the rights and responsibilities of software modules to ensure program correctness”. It is a contract by which a routine may have some expectations:

Preconditions: The routine’s requirement. According to [HT00], “a routine should never get called when its preconditions would be violated” and “it is the caller’s responsibility to pass good data. It is its responsibility.” If the caller can’t assure pass good data, has to decide what to do, how to handle it. Again, it is a requirements thing, a design decision.
Postconditions: The state of the world when the routine is done.

Another benefit of this technique is to detect problems as soon as you can, being able to crash the program earlier, which is better than continuing with corrupted data. “When your code discovers that something that was supposed to be impossible just happened, your program is no longer viable”

But not all languages support DBC in the code. In languages such as C, writing the contract as a comment gets you still a very real benefit. Moreover, it is possible to emulate this using assertion. We will see later.

A lot of authors follow the idea that run-time checks add unneeded complexity and that it is worthy to replace it with asserts and thorough integration testing. One of the classics’ uses of assertions is to check assumptions like that an input parameter’s value falls within its expected range (or an output parameter’s value does) or that a pointer is non-null.

Nevertheless, a function that tests a condition and crashes if the condition is not fulfilled may be OK for debugging, but in most cases is not flexible enough in production code. Or maybe yes, it is the only sensible option. Again: it is a design-architecture-requirements thing. One workaround could be to use assertion in the development phase, while debugging, and turn it off in release code. The problem is that in order to certificate the software, with that workaround we would be in the same place. Although the code quality will be better, a static analysis tool would be throwing the same warnings.

Defensive Programming

Some may say that DBC and defensive programming are kind of the opposite, but [McC04] includes assertions to check preconditions inside its chapter of Defensive Programming, as a way to handle garbage-in:

“The main idea is that if a routine is passed bad data, it won’t be hurt, even if the bad data is another routine’s fault”. You take responsibility even when it is other’s fault. @rsrajan1 gives us another good definition: “The idea is not to write code that never fails. That is a utopian dream. The idea is to make the code fail beautifully in case of any unexpected issue”.

The main way to handle garbage-in is checking the values of all routine input parameters and once you’ve detected an invalid parameter, deciding how to handle bad inputs.

Depending on the situation, you might choose any of a dozen different approaches. [McC04] in Section 8.3 Error-Handling Techniques, describes in detail some of them (return neutral value, substitute the next piece of valid data, return the same answer as the previous time…). How to decide? Again, McConnel insists: “Deciding on a general approach to bad parameters is an architectural or high-level design decision and should be addressed at one of those levels.” The way in which errors are handled affects the software’s ability to meet requirements related to the correctness, robustness, and other nonfunctional attributes.

The conclusion

To summarize, the most important thing to have into account is the need for high-level decisions about what to do with bad input. Once this is clear, take advantage of design techniques such as BDC of features of the language to approach the solution. In the next post, a solution based on C and assertions would be proposed.

References

[HT00] Andrew Hunt and David Thomas. 2000. The pragmatic programmer: from journeyman to master. Addison-Wesley Longman Publishing Co., Inc., USA.r

[McC04] Steve McConnell. 2004. Code Complete, Second Edition. Microsoft Press, USA

[Mey97] Bertrand Meyer. Object-Oriented Software Construction. Prentice Hall, Englewood Cliffs, NJ, second edition, 1997.

Original post in myram

Overflow in integer arithmetic with C

J. Marchán — Tue, 11 Jun 2019 18:47:48 +0000

Overflow

Sometimes, the results of working with integers may go outside the range that can be represented, that is, when the result of operating on two k-bit numbers is a (k+1)-bit result. Static analysis tools such as Polyspace or Sonar may also trigger a warning on an operation or in the worst case, you come upon an error in run time.

Typically, addition and multiplication are the sources of overflow, but it can appear with subtraction and the abs function.

How to overcome the problem

Up-casting to a larger size.

The first proposal requires to know the maximum (or minimum) value of the types you are working with. If so, it is possible to do something like this:

#include <stdint.h>

int16_t add_without_overflow(int16_t x, int16_t y)
{
  int32_t z = (int32_t) x + y;

  if (z > INT16_MAX)
  {
        z = INT16_MAX;
  }
  else if (z < INT16_MIN)
  {
        z = INT16_MIN;
  }
  return (int16_t) z;
}

This piece of code upcast the addition to larger type size, from int16 to int32, from two k-bit numbers to (k+1)-bit number. Afterward, check for overflow. That is, if your result fits in the k-bit number, you got it.

To compare with a well-known domain value

Maybe is not so easy to know the maximum or minimum or a certain type in the target platform. In that case, an easy way to overcome is to check the operands with a maximum or minimum of your specific domain. Suppose that we are operating on two variables which stand for the weight of two loads in grams. But we are guaranteed (by system requirements) that no load can be heavier than 5.000 grams.

It can be just put:

int16_t add_without_overflow(int16_t x, int16_t y)
{
  int16_t total = 0;

  if (x <= MAX_LOAD_WEIGHT &amp;&amp; y <= MAX_LOAD_WEIGHT)
  {
        z = x+y;
  }

  return total;
}

Furthermore, that way the correctness of the data is checked.

Nevertheless, this approach have a drawback in my opinion. You need you be very careful with the domain ranges. Imagine that the maximum of the load could be 40,000. An addition of two the heaviest loads (40,000+40,000) results in an overflow.

In my opinion, that would be a valid solution when your domain values are far away from the limits of you type size.

References

Here can be found more precise and detailed explanations

Understanding and Preventing Overflow
Catching overflows in C
Understanding integer overflow in C/C++

Original post in myram

Software as a product of intellectual activity – Reflections on software development

J. Marchán — Wed, 28 Nov 2018 17:37:31 +0000

What is software development?

Software development involves far more than the mere production of code. It goes beyond writing instructions and knowing specific syntax and grammar rules. So, we may well ask ourselves: what is software and how is it developed? One of the best examinations of this subject was done by Peter Naur – creator of the BNF notation and winner of a Turing award – in his essential article “Programming as Theory Building”. Here’s a summary of his idea.

Naur uses Ryle’s notion of theory as a starting point. In The concept of Mind, a classic work of philosophy on the nature of the mind and human behavior, Ryle develops his notion of theory as part of his analysis of intellectual activity and the manner in which this differs from activity that is merely intelligent. What characterizes the first versus the second is that for intellectual activity the person builds a theory. This theory is understood as the knowledge a person must have in order not only to do things intelligently and well according to certain criteria, but also to be able to explain, answer questions, argue or justify the activity of concern. Having a theory allows the person to detect and correct lapses, to learn from examples, and so on. It should be noted that this notion does not rely on the idea that intelligent behavior depends on following or adhering to rules or methods. For example, to understand Newton’s theory of mechanics, it does not suffice to know that force is equal to mass times acceleration; rather, a person must have an understanding of the way in which Newton’s laws apply to certain aspects of reality so as to be able to recognize and apply the theory to other similar phenomena.

From Ryle, Naur borrows the idea of theory and argues that what has to be built by the programmer is a theory of how certain aspects of the world will be modeled, represented and handled by a software system. This person is able to respond to any demand for modification or adaptation to any change in requirements.

Implications for software maintenance

A software program’s life after delivery, that is, its maintenance (remember that this is what occupies most of the life cycle) depends on the people who are responsible for said program having this theory. If the programmer team that possesses the theory is dissolved, the deep knowledge of that materialization of a real problem in code form is lost, producing the death of the software program. The program can continue to be executed, but modifications and enhancements will become increasingly expensive and technical costs will increase.

The theory is a collective property shared between members of the original programmer team. Naur argues that for new generations of programmers to prolong the life of software, it is more important for them to work closely with the original programmers – to learn how the software works and how unexpected program reactions and modifications can be understood within the program theory – than it is for them to become familiar with the code and documentation (though this will certainly help). Thus, communication and the human factor become an important part of software development.

One important consequence of this view is that rebuilding a software program’s theory from documentation alone is impossible. Or the classic Brooks Law, which states that adding manpower to a late software project makes it later.

Conclusions

The fact that programmers spend a considerable amount of development time trying to understand code is a problem intrinsic to software development. What we as programmers are unconsciously doing – though we may know nothing of Naur or Ryle’s Building Theory – is trying to rebuild the theory, to create that mental vision. And this is so because programming belongs to the realm of intellectual, and not merely productive, activity. Therefore, it is still a particularization of the traditional creation problem. An experienced engineer, with a deep knowledge of the problem domain, is able to solve related questions in a way that is consistent with the theory. Why are they always coming up with better and faster ideas? The Austrian writer Stefan Zweig, who was interested in the mystery of creation (artistic, not software) throughout his life, once said that “of all the mysteries of the universe, none is more profound than that of creation […] and who could say where ideas come from?” At least in the case of software, we can say that theory plays a part.

Original published in myram

References
– Peter Naur, Programming as Theory Building
– Ryle, G. The Concept of Mind
– Javier Garzás, Comprendiendo qué es crear software

Unequally distributed quantity

J. Marchán — Tue, 06 Nov 2018 20:04:19 +0000

Suppose that you have to divide or to distribute a quantity in three (maybe a rent payment), but you want to do it unequally.

It can be done more or less mentally, but I wanted to have
quickly all the possibilities and decided to write some code to do it.

I though how it is done mentally. For instance, dividing 990 units in 3 parts:

You have three parts of 330 each one
Subtract 5 to one and add it to another
Repeating that you obtain different possibilities to divide initial quantity

Translation to code.

First approximation to the problem was to establish a minimum that each person would pay. Let’s to say 250. 250×3= 750, so it remained 240 units to share out.

I wanted a granularity of 5 units, so there was in fact a 24/5=48 items (of 5 units) to share out.

It was not trivial for me to lay out the problem until I realized that this matched with some well known combinatorial problem that I didn’t remember. After a search I found exactly what I was looking for: Start and bars
It can be used to solve many simple counting problems, such as how many ways there are to put n indistinguishable balls into k distinguishable bins.

It can be easily done with Python using combinations function

 import itertools

def combinations(n, k):
    return itertools.combinations(range(n), k)

def calculate_rent(n, k):
    for c in combinations(n, k):
        if sum(c)==n:
            yield c

combinations(n,k) return r length subsequences of elements from the input iterable n. Afterwards, we only want subsequences whose sum of the k bins be equal to n.

Just left to write some auxiliary code in order to print the list. Due to what we have obtained is a list of ways to put n indistinguishable balls (48) into k distinguishable bins (3), it is necessary to multiply each ball by our granularity (5) and sum the minimum.

total = 990
minimum = 250
people = 3
granularity = 5
remain = total - minimum*people
rent_combinations = calculate_rent(remain/granularity,people)
for rents in rent_combinations:
    print([5*i+minimum for i in rents])

Below is displayed a partial screen-shot of the 192 total elements of the output.

Original post in myram

A dummy blockchain implementation in C (II)

J. Marchán — Thu, 25 Oct 2018 18:22:07 +0000

A dummy blockchain implementation in C (I)

1. Parties

All the ingredients are ready, so now it is time to code the main function. As I already said, it is going to be a voting system. For that, I have created the next enum with all the parties available in the electoral system:

typedef enum party_code_t {
GOOD_PARTY, MEDIOCRE_PARTY, EVIL_PARTY, MAX_PARTIES
} party_code;

And a function which randomly gets a vote:

static party_code get_vote()
{
    int r = rand();
    return r%MAX_PARTIES;
}

2. First block: genesis

NODE *head;
    DATA genesis_element;
    init(&head);

    transaction genesis_transactions = get_vote()};
    block_t genesis_block = {0, string_hash(genesis_transactions), genesis_transactions};
    genesis_element.info = genesis_block;
    head = add(head, genesis_element);

In order to create a new element are necessary three steps:

1. To create the transaction. We create a transaction getting the name of the party.
2. To create the block with its three fields: previous hash, current hash and a transaction.
3. To create the node element of the list (the block) and to insert it to the list.

It is common to call the first block in a blockchain as genesis. As there is no previous block, we set the previous block hash to zero.

3. Adding votes

  int previous_hash = genesis_element.info.previous_block_hash;
    for(i=0;i<nvotes;i++) {

        DATA *el
        block_t *b;
        transaction t = {get_vote()};

        b->block_hash = string_hash(t);
        b->transactions = t;
        el->info = *b;
        previous_hash = b->block_hash;
        head = add(head, *el);
    }

Once the first element has been inserted, it is possible to create a loop to create as many blocks as wanted. It follows the three steps from above.

That is all. After compiling and executing we can read the output in the terminal. Each vote (or block) is displayed below the previous one, and it is formed by the hash of the previous vote, the current hash and the name of the voted party. Its current hash it is formed by all the votes previously submitted.

You can see the final code here. The core is the snippets showed in the post, but more auxiliary code has been added, mainly to print the linked list.

Original post in myram

Disclaimer: This article is full of simplifications and abstractions in order to get the fundamental. Although one of the key points of blockchain is that database isn’t stored in any single location but it is shared and transactions are spreading to a P2P network of nodes, here is obviated all the network part.

A dummy blockchain implementation in C (I)

J. Marchán — Mon, 22 Oct 2018 16:46:55 +0000

Voting with Blockchain

Hundreds of thousands of articles have been written about blockchain and how it is going to change the world. I am not to talk why I don’t understand how this can be possible. Neither Bitcoin, which (from my misinformed point of view) it is just a way to people trying to earn dollars: the ultimate goal of bitcoiners is wait enough time and change them to dollars (sincerely, where is the revolution?).

But this is not the topic. This is a description step by step of a blockchain algorithm implementation in C. And in order to vary a bit, instead a money transactions it is going to emulate a voting system.

Firstly, it is necessary to understand the basic concepts of blockchain. If you still don’t know it I recommend you this, this and this 5 minutes introduction video.

Now all we know what a transaction, block and hash are we are ready: Blockchain is very easy in its core. It is formed by a well-known data structure in computer science: Linked list.

1. The block

typedef int hash;
typedef char *transaction;

typedef struct Block_T {
    hash previous_block_hash;
    hash block_hash;
    transaction transactions;    
}block_t;

It is declared a block with the hash of the previous block, the hash of the current block and a transaction. Instead of a set of transaction, the block has just one transaction: a single string of characters.

2. The hash

int string_hash(void *string)
{
    /* This is the djb2 string hash function */
    int result = 5381;
    unsigned char *p;
    p = (unsigned char *) string;

    while (*p != '\0') {
        result = (result << 5) + result + *p;
        ++p;
    }

    return result;
}

This function, copied from somewhere, take a string of characters and return an integer which is the unique hash.

3. The list

I will not explain either how a list woks since it is a very basic data structure and it is easy to find resources on Internet. However, it was not so easy for me to find a clear, clean and simply implementation of lists in C. So I take one and adapted it.

typedef struct {
    block_t info;
} DATA;

typedef struct node {
    DATA data;
    struct node* next;
} NODE;

The data of the nodes of our list is the block_t structure defined previously.

NODE* add(NODE* node, DATA data);
void print_list(NODE* head);
NODE * reverse(NODE * node);
void get_list_transactions(NODE* head,unsigned char *list_trans);

And the main functions of the list is add, in order to insert new nodes at the end, and print, which is going to show the node data information, which is the block.

Those are the main ingredients. In the next post I am going to put everything together to see a blockchain running.

(Original post in myram)