Watch Your Step!

(Note: if you are familiar with SQL injection vulnerabilities, you may want to skip to the end of this post, which mentions some new research that could eliminate such errors before they are made.)

This classic comic from xkcd demonstrates one of the most common and dangerous type of security vulnerabilities in web applications, called SQL injection.  This is a way in which an attacker can cause the application to execute unintended and unanticipated (by the application operator) actions on the database.  In this example, the action is to remove the database table called "Students," thus removing all student information.

The application server executes some code in response to receiving information submitted from a web form.  I will show the example in Java, but similar code is written in other languages, including PHP, Perl, and .NET.  The application sends a query to the database; in this example, it tries to get student information.  The query is typically coded in SQL, and may have a form similar to this:

SELECT * FROM Students WHERE NAME = 'name'

The name itself, shown above in italics, is of course different for each student; the value of this field is taken from the web form.  The code that generates this query in Java looks like this:

String query = "SELECT * FROM Students WHERE NAME = '" + request.getParameter("name") + "'";

This builds the query string from three parts: two constant strings, and the call request.getParameter("name"), which returns the "name" field of the web form.  Unfortunately, if you substitute little Bobby Tables' name into this computation, you will end up with the following SQL statement:

SELECT * FROM Students WHERE NAME = 'Robert';
DROP TABLE Students;
--'

(Bobby's full name is shown in red; note that the final single quote comes from the second constant string in the original computation.)  When this string is sent to the database for execution, it will be interpreted as three different commands, shown above on three separate lines.  The first will indeed return the information about Bobby, but the second will remove the Students table.  The third consists only of the three characters --' ; the first two dashes indicate that this is a comment and the rest of the line (the trailing quote) is to be ignored.

This is not funny!  All too many web applications are written in this way, and are therefore vulnerable to SQL injection attacks.  In OWASP's list of top 10 vulnerabilities, injection vulnerabilities appear as the first item, tagged as being common, easy to exploit, and having severe impact.

How can such problems be avoided?  Obviously, any user-supplied information, including the contents of web forms, must be validated or sanitized.  Validation means blocking any potentially-dangerous input (such as anything that includes quotes), while sanitation means modifying such inputs to a non-harmful form.  This is easy enough to do; any reasonable web-development framework will supply appropriate validation and sanitization functions.  However, the developer must remember to call these functions on each and every user input; any omission creates a security vulnerability, and a systematic attacker will discover it eventually.

An alternative solution is to use prepared statements to communicate with the database.  Java, like other server-side programming languages, offers more than one interface to the database.  A prepared statement uses a fixed SQL statement, which includes question marks instead of actual parameter values.  Bobby's example would look like this:

SELECT * FROM Students WHERE NAME = ?

When a prepared statement is used to invoke a database operation, all parameters identified by question marks are given their actual values by invoking type-specific methods (such as setString or setInt) on the prepared statement object.  These take care of sanitization internally, so that the developer doesn't need to worry about it.  A prepared statement object can therefore be used multiple times with the same SQL query but with different arguments.  Another advantage of prepared statements it that the query string they receive must obey SQL syntax rules (with the addition of the question marks), and this can be checked when the prepared statement is initialized with the query, and the query can also be optimized once instead of having to be optimized for each call.

However, there is a serious problem in the approach taken by all these languages that require the construction of SQL queries as strings.  This gives too much freedom to the developer, allowing the creation of security and other errors that will not be discovered until the application is actually run.  Certainly, if you use a statically-typed language like Java, you should also be able to express the syntax of your database queries in a way that can be checked for correctness at compile time rather than at runtime.  This calls for a syntactic extension of the programming language, which will support SQL statements with parameter indicators such as the question marks of prepared statements.  This will have the advantage of catching syntactic erros at compile time, as well as the possibility of adding sanitation automatically, as is done for prepared statements.

Current web-development languages make it difficult for developers to do the right thing, necessitating special tools for discovering security vulnerabilities and fixing them.  Why not provide the ability to prevent them in the first place?

This is actually possible.  In their paper "Simple and safe SQL queries with C++ templates" (Science of Computer Programming 75 (2010)), Joseph Gil and Keren Lenz describe a system that uses C++ template metaprobramming techniques to represent relational algebra expressions inside the C++ language.  (Relational algebra is an alternative to SQL with a more mathematical syntax.)  The compiler can check the expressions written this way for syntactic correctness, and when the SQL query is actually built for sending to the database, all string inputs are sanitized so that they can't modify the syntax and create injection attacks.  Bobby's example can be written in this system this way:

(Students / (NAME == name)).asSQL()

The parenthesized expression is the relational-algebra form of the query, and the asSQL() method converts it to a string that can be sent to the database.  This syntax uses C++ operator overloading, and is therefore inapplicable to Java and similar languages.  It is possible to extend these with similar capabilities using more cumbersome syntax, but the right thing to do would be to make SQL (better yet, relational algebra) an integral part of the language.  Anyone who has ambitions to develop the next server-side programming language should be aware of this research!

The Weakest Link

The May 2011 issue of Communications of the ACM contains an article called Weapons of Mass Assignment by Patrick McKenzie.  The article describes McKenzie's security analysis of the pre-release source code of Diaspora, an attempt to build a "privacy-aware Facebook alternative".  The Diaspora home page makes the following claim: "Inherently private, Diaspora doesn’t make you wade through pages of settings and options just to keep your profile secure."  Unfortunately, McKenzie was "struck by numerous severe security errors", which were "serious enough to jeopardize the goals of the project."

The first kind of errors McKenzie reports are a result of confusion between authentication and authorization.  Authentication means that the system has identified the user using some secure mechanism, so that nobody else can impersonate that user.  Authorization, on the other hand, refers to the set of operations that a user can legally perform.  Naturally, authorization is meaningless without authentication, since you can't refer to the operations a user is permitted to perform without authenticating that user.  But authentication isn't enough; once you know who the user is, you should allow him to perform only operations he is authorized to perform.

In the code release that McKenzie examined (the "pre-alpha developer review"), an authenticated user could delete photos based on their IDs.  If you knew the ID of somebody else's photo, you could delete it, and discovering photo IDs was easy.  Here is an example of a URL (from another source) that contains IDs: http://ark.intel.com/Product.aspx?id=52215&processor=i7-2600S&spec-codes=SR00E.  The part that follows the question mark (shown here in bold) contains a list of parameters and values, which the server-side script accesses to figure out what to do.  When you see such URLs, you can often figure out what the IDs refer to, and you can replace IDs in them to create various effetcs.  In Diaspora, for example, you could delete one of your own photos to see what that request URL was like, and then replace the photo ID to delete somebody else's photo.

Diaspora uses Ruby on Rails, and suffers from the security vulnerabilities of that platform.  In particular, McKenzie points to the Rails feature of "mass update", which is a convenient but dangerous programming tool.  It takes a list of keys and associated values and calls the related accessor method for each key.  This allows an attacker to add keys that the developer didn't intend to be modified, thus creating serious security vulnerabilities such as allowing one user to take over another's account.  If mass update is used on values received from an HTML form (which is often the case), all an attacker needs to do is modify the form to send malicious key-value pairs.  Because the form is presented on the attacker's machine, this is an easy task.

McKenzie details several other vulnerabilities, which allow attackers to discover or replace another user's encryption key, thus allowing them to decipher all that user's previous and future communications with the server.  This is quite serious in an application whose first priority was security and privacy.  A chain is only as strong as its weakest link, and this applies first and foremost to security, where an attacker will deliberately go after the weakest link.  The fact that Rails has mass update enabled by default should make you suspicious of any application built on Rails, since it requires positive action by security-conscious developers to disable mass update.  The more issues developers need to be careful of, the greater the chance that they will miss some, creating security vulnerabilities.  This makes me question whether Rails is a good tool for developing secure web applications (see The Right Tool for the Job).  This is unfortunate in tool whose main purpose is to make web development easy.

It remains to be seen whether Diaspora will finally be secure.  McKenzie ends his article on a positive note: "This is not a reason to despair, though: every error fixed or avoided through improved code, improved practices, and security reviews offers incremental safety to the users of software and increases its utility."  I am less optimistic: an application that boasts its security needs to designed for security from the first, not debugged and reviewed to decrease its vulnerabilities after the fact.

Covariance and Contravariance

Type declarations on method parameters and return values are also constraints on the possible values that can be passed between a method and its caller.  As such, they form part of the contract for the method.  This is, in fact, a required part of the contract in statically-typed languages.  (Unfortunately, this is typically the only part of the contract that gets written.)

Suppose you have a class called Complex representing complex numbers, and a method that adds two numbers and returns the result.  In an object-oriented fashion, the method signature will be Complex add(Complex other), and a call c1.add(c2) will add the numbers c1 and c2 and return the sum.  The type declaration "Complex other" in the method signature is a precondition that requires callers to pass only objects of type Complex to this method, and the declaration that the result is Complex is a postcondition ensuring that only Complex objects will ever be returned by the method.

Normally, we don't really think of type declarations as a contract, since they are enforced by the compiler and no further action is required by the programmer to ensure that the contracts are indeed satisfied.  But if you think of type declarations as contracts in the context of Liskov's Behavioral Subtyping Principle, they have interesting consequences.  One is that subclasses are only allowed to strengthen postcondition but never weaken them.  This means that subclasses may return more specialized types than Complex.  This is not surprising; it is quite likely that there are several implementations of complex number, all of which are subtypes of Complex; for example, ComplexAsCartesian and ComplexAsPolar, referring to the two most common representations of complex numbers.  It is perfectly permissible for the add method of each subclass to return elements of that subclass (although that is not always the best policy).  But can you redefine the return type of ComplexAsCartesian.add to be ComplexAsCartesian rather than just Complex as in the superclass?  The answer depends on the programming language, and even on the language version.  For example, Java originally didn't allow any changes in method signatures, but since Java 5 it is possible to redeclare more specific types (that is, subtypes) for method return values.

This kind of change, where subclasses use subtypes of those used in their superclasses, is called a covariant change, since the direction of change is the same: as you go down the inheritance hierarchy, types get more specialized (that is, also go down).  Covariance is very natural to use in practice.  In addition to the example above, you can think of modeling artifacts (physical or virtual) that need to be connected in various ways.  Often, as you become more specific in one dimension, you need to be more specific in others.  For example, every laptop needs a power supply.  But specific laptops have dedicated power supplies, and you can't use any power supply with any laptop.  So the most abstract Laptop class may define an attribute called powerSupply, whose type is PowerSupply.  But an ABCLaptop requires an XYZPowerSupply, so the type of the power supply goes down the hierarchy as the type of the laptop goes down.

Covariance is all very well for method return types, where it fits the Behavioral Subtyping Principle.  But it contradicts the principle for method arguments.  The type of a method argument is like a precondition, since it constrains the values that the caller can pass to the method.  Preconditions may only be weakened in subtypes; this means that argument types can only be generalized in subtypes.  This is called contravariance, since argument types to up the hierarchy in subtypes.  So here we have a conflict between what is theoretically correct (contravariance for argument types) and what is useful (covariance).

There is a large debate on this issue, and different languages treat it differently.  None of C/C++, Java, or C# allow any change in argument types (this is called invariance).  This is, in fact, unrelated to the issue of covariance versus contravariance; it is a consequence of the fact that these languages support overloading (see Overriding and Overloading).  As a result, any change in method argument types defines an overloaded method, which is unrelated to the original method.  Eiffel follows the practical route, supporting covariance of argument types, and incurring the inevitable cost.  This cost is the lack of compile-time type checking for these cases.  In statically-typed languages, including all the ones mentioned above, we expect the compiler to type-check the program so that no type violations will occur at runtime (with some other notable exceptions, such as type casting and some uses of generics in Java).  Covariance creates another exception to this rule.

Of course, preventing covariance in the language doesn't solve anything, since in practice it is still necessary.  What programmers do when the language doesn't support covariance is to write their own tests in subclasses, checking for the correct subtypes and throwing exceptions when they are incorrect.  So even though the program is fully type-checked, there are still type-related exceptions at runtime.  But because these are programmed manually rather than being thrown by the language runtime, language designers feel it isn't their responsibility.  This ostrich effect is, of course, completely pointless.

Abstract Preconditions

Returning to the example of the Set type, suppose now that its implementation ArraySet uses a fixed-size array to hold the set elements, and is therefore limited in size (or "bounded").  The maximum size, called the set's capacity, is given when the ArraySet object is constructed and the array is allocated.  The method ArraySet.add, which can add a new element to the set, now needs to have a postcondition size() < capacity(), where size() returns the current size of the set and capacity() returns the maximum size.

Side note: in such cases, it is common to provide the size() method, but less careful designers don't provide capacity().  The assumption is that you ought to know the capacity, since you gave this value when creating the set.  But, of course, you may be using a set created by someone else.  Writing contracts often alerts you to the necessity of adding such informative methods.

According to Liskov's Behavioral Subtyping Principle (see The Correct Use of Inheritance), ArraySet may not strengthen a method precondition.  Therefore, Set must also declare the same precondition (or a stronger one) on the add method.  In general, however, sets don't need to be bounded, and therefore this precondition is inappropriate there.  What is wrong?  The first thing to question is the inheritance hierarchy: is ArraySet really a subtype of Set?  More generally, are bounded sets types of sets?  At first blush, the answer is obviously yes.  But on deeper thought, it seems that we have our abstractions a little bit off.  There are really three concepts involved here: general sets, bounded sets, and unbounded sets.  Both bounded and unbounded sets are kinds of sets; bounded sets have the size() < capacity() precondition, while unbounded sets don't.  Again, it seems like general sets must have this precondition as well, to comply with the Behavioral Subtyping Principle.

Certainly, general sets need to have some precondition that subsumes the boundedness condition, but it doesn't need to have the same form.  The abstract meaning of the precondition is that the set may not be full when adding a new element.  In this form, the precondition is applicable to any set; bounded sets may sometimes be full, while unbounded sets will never be full.  So we need to add  to the Set type, which represents general sets, a method full() that returns a boolean value.  The precondition on Set.add will be !full().  At this level, this precondition is abstract: its precise meaning is unknown.  A client that uses an object of this type therefore needs to check that the set isn't full before adding an element.  The implementation of Set.full may provide some default value, or may be absent, in which case the Set type itself is abstract.

ArraySet.full overrides Set.full to return the value of the expression size() < capacity().  In addition, this method has a postcondition $ret == size() < capacity().  Clients of ArraySet now know the precise condition under which they are permitted to call the add method.  In contrast, unbounded implementations of Set, such as HashSet, override Set.full() to return false, with a postcondition $ret == false (or !$ret).  Clients of HashSet therefore know that the precondition on add is really vacuous: it will never be true, and therefore they are allowed to call add under all circumstances.

If the concepts of bounded and unbounded sets are deemed important enough, it is possible to define them as classes (or interfaces) in their own right, and put the relevant contracts there.  In this way, the missing abstractions are crystallized in the design, with precise contracts that obey the Behavioral Subtyping Principle without forcing a formulation of the precondition that is specific to a subtype.

Overriding and Overloading

Two terms that sound similar and are sometimes confused are overriding and overloading.  The former is an essential part of inheritance, and therefore of object-oriented programming; the latter is a syntactic device that adds no expressive power to the language.

Overriding a method means providing a new implementation for it in an inheriting class.  This may be necessary because the subclass has a different representation, which has more information than the superclass.  For example, suppose you are programming an interactive game, in which characters lose health points as a result of exertion or by attacks by other players.  This is implemented through a method damage(int points), which inflicts the given amount of damage.  Now assume that you create a special kind of character, called Merlin, which can make itself invisible as well as operate a force shield that protects it from certain kinds of enemy actions.  However, it can't perform these new functions when its health is too low.  The class implementing the Merlin character inherits from the general character class.  It needs to override the implementation of the damage method, in order to disable invisibility and the force shield if the health level drops below the relevant thresholds.  When the damage method is called for any character, it decreases its health; for Merlin, it may additionally disable his special abilities.

The choice of which code runs for a particular invocation of the damage method is made at runtime.  If the character happens to be Merlin (that is, its type is the Merlin class), the code executed will come from the Merlin class.  If the character's type is another class, the code will be taken from that class, or from the closest ancestor class that provides an implementation of that method.  This is called dynamic dispatch, and is a cornerstone of object-oriented programming.

Merlin's special abilities can be damaged by special types of attacks, which do not otherwise damage his overall health.  It seems natural to add to Merlin's class a new method, damage(Ability ability), which damages the given ability but does not affect other abilities or the health measure.  This is a case of overloading: using the same name for two different methods.  Many, but not all, object-oriented languages support overloading.  Java, C#, and C++ all do, while Eiffel doesn't.  The choice of which code gets executed in a call to the overloaded damage method is made by the compiler: if the argument is an int, the general damage method will be called; if the argument is an Ability (that is, its type is the Ability class), the second will be called.  These types must be known at compile time; if they aren't, the program won't compile.

Because the decision of which overloaded method to call is static, it is known to the programmer writing the call.  Therefore, overloading can always be replaced by renaming methods.  In our example, the new method that damages Merlin's special abilities can be called damageAbility to remove the overloading.  In fact, overloaded methods are implemented using this technique; languages such as C++, Java, and C# have a special notion of method name, which attaches encoded information about argument types to the method name as defined by the programmer.

When used properly, overloading can make programs more understandable.  For example, the + operator is overloaded in Java to represent addition of integers as well as floating-point numbers.  That's perfectly understandable, since the mathematical addition operator applies to all these types and has the same properties for them (associativity, commutativity, etc.).  It would be perfectly fine to use + for adding complex numbers if Java allowed this (and is common in C++, which does).  However, Java overloads + to denote concatenation of strings as well.  This is confusing, and is a design error of the language.  This error is compouned by the fact that + coerces its arguments to more general types, so that x + y will denote floating-point addition if x is an int and y is a float, but string concatenation if x as an int and y is a string.  Worse yet, mathematical properties of addition don't hold for string concatenation, and as a result ("a" + 1) + 2 is "a12" while "a" + (1 + 2) is "a3".

Because overloading doesn't add to the expressive power of the language, and is a trap for the unwary, it should be removed from object-oriented languages.  Unfortunately, the C++/Java/C# family of languages encourage overloading, and even require it in the case of constructors, whose names must be the name of the class.  Suppose you want to create a complex-number class called Complex, and give it two constructors, one receiving the rectangular representation of the number (x and y for x+iy) while the other receives the polar representation (rho and theta for rho*e^(i*theta)).  You want to call these two constructors by descriptive names, such as complexFromRectangular and complexFromPolar.  But in C++/Java/C#, both must be called Complex!  Not only are the names non-descriptive, they also coincide, because both constructors take two arguments of the same types.  I won't describe the contortions that programmers of these languages have to go through to solve this problem.

My recommendation: avoid overloading altogether.  If you really feel it's essential in some case, at least make sure that the overloaded methods have the same semantics (as in the case of mathematical addition).  If you use overloading in other cases (such as addition and concatenation), you will have only yourself to blame when you get confused; and your users will be perfectly justified in blaming you when they, in turn, get confused.

Writing Contracts

In the best thriller tradition, we left our hero, the Set type, in an awkward position at the end of the last episode.  Because Set has a subtype, HashSet, that doesn't allow nulls as values, the method Set.add(Object x) needed to have a precondition x != null.  But Set has another subtype, ArraySet, which does allow null values.  Therefore, we couldn't put a postcondition on Set.get() that guarantees that the returned value won't be null.  The Set type now precludes null inputs, but may return null values; this seems inconsistent.  Yet both contract decisions seem to be forced by Liskov's Behavioral Subtyping Principle!

In such cases, it is often helpful to look for missing abstractions.  Here, there is an obvious correlation between null inputs and outputs: some sets support null values in both cases, and the others don't in either.  The Set type should clearly distinguish between the two types of sets, by means of a query such as supportsNullValues().  The precondition of Set.add(Object x) will now be:

!supportsNullValues() ==> x != null

where "==>" denotes logical implication.  The postcondition of Set.get() will be:

!supportsNullValues() ==> $ret != null

where "$ret" denotes the returned value.  The contract for Set is now consistent in both cases.  If supportsNullValues() is true, the precondition on add and postcondition on get are inactive; if it's false, both are active.

Furthermore, we can now add a postcondition to HashSet.supportsNullValues(): $ret == false (or, equivalently, !$ret).  As a result, developers using HashSet know, by examining the contract, that add must not be given null values and get will never return null.  Similarly, ArraySet.supportsNullValues() will have a postcondition $ret == true (or simply $ret).  Developers using ArraySet will now know that they can provide add with null inputs, and may receive nulls from get.  Developers who use the Set type without knowing the particular implementation can act in one of two ways.  First, they can be cautious and not insert any null values into the set.  Because Set.get will only return elements previously inserted into the set, it won't return null in this case.  (Note that this is part of the contract that is difficult to specify formally, since it involves conditions on the behavior of the set over time.  However, it is an important part of the contract, and should be documented as such, using natural language.)  The second option is to call supportsNullValues() and act according to the value returned.

In the example, Set.add had another precondition that stated that the client is not allowed to add to the set an element that is already in it.  This is legal but not recommended.  In general, preconditions should contain any conditions under which the action of the method is not well defined.  For example, it makes no sense to ask for an element of an empty set, which is why Set.get has a precondition that the set isn't empty.  But adding to the set an element that is already there is perfectly well defined; the set simply doesn't change.  Instead of requiring clients to check this condition before calling add, the implementation of the add method should simply do the right thing and not add the element if it already exists in the set.  A little effort on the part of the implementer can save much effort for clients.

The Correct Use of Inheritance

Perhaps the most subtle relationship in object-oriented programming is that of inheritance.  Many object-oriented languages, including Java, distinguish between classes and interfaces, as a reaction to the problems languages such as C++ faced with multiple inheritance.  This is a complex issue I will address in a later post.  Now I want to focus on the logical relationships involved in inheritance.  In order to avoid the class/interface dichotomy, I will use the notion of a subtype.  A type A is a subtype of B if it inherits from it, whether both A and B are classes, both are interfaces, or A is a class and B is an interface.  (Java uses the verb "extends" for the first two cases and "implements" for the third.)

An element of a subtype A may be used whenever an element of the supertype B is indicated.  For example, suppose we have a type called Set that represents mathematical sets.  It has a number of implementations inheriting from it, including ArraySet, which holds the elements of the set in an array, and HashSet, which holds the elements in a hash table.  The Set type has various methods, including add(Object x), which adds an element to the set; get(), which returns an arbitrary element of the set; and has(Object x), which returns true if and only if x is in the set.  Since a set can't contain the same object multiple times, we put a precondition on add(Object x) requiring that x is not already in the set: !has(x).

Unfortunately, our HashSet implementation doesn't support null as an element in the hash table, so we add another precondition to add(Object x), stating that x can't be null: x != null.  Now, suppose we have a client C that uses our code, and receives a parameter s of type Set.  When the programmer of the client code reads the contract for Set, he sees only one precondition: !has(x).  He will certainly be careful not to insert the same element twice, for example by using the following code:

if (!s.has(element)) s.add(element);

But he has perfect confidence in the following piece of code:

if (!s.has(null)) s.add(null);

He will be rudely surprised, therefore, when this actually bombs on him somewhere inside the call to add in our HashSet implementation.  He may not even have known about the existence of HashSet, since he received the object s, which happened to have this type, as a parameter.  He is the proverbial innocent bystander, and should be protected from this kind of problem.  After all, he kept his side of the contract, and has every right to expect us to keep our side!

This demonstrates a general problem, which will manifest itself whenever the precondition of a method in a subtype is stronger (that is, requires more) than that of the supertype.  The rule must therefore be that subtypes are not allowed to strengthen method preconditions.  We will have to add a precondition to Set.add, to warn potential users that some subtypes may not accept null as a parameter.  Our ArraySet implementation can now weaken the precondition by removing this requirement.  This is perfectly legal; clients that use ArraySet objects through the Set supertype will not be allowed to call add(null), but clients that use ArraySet directly will be able to enjoy the extended functionality.

Since we restrict Set.add not to accept null parameters, it looks like we can now put a postcondition on Set.get, stating that it will never return null.  This will work well for HashSet, but will fail for ArraySet, which does accept null elements.  By adding this postcondition to Set.get, we have again harmed innocent bystanders; in this case, a client of Set who happens to receive a HashSet object as its own parameter.  Such a client feels perfectly justified in writing the following code:

if (!s.isEmpty()) System.out.println(s.get().toString());

He is careful to check the precondition of get, which states that it can't be called when the set is empty, and he is therefore entitled to rely on get's postcondition and to expect that no NullPointerException will be raised on the call to toString.  He may not even be aware of the existence of ArraySet, and of the fact that it doesn't have this postcondition.  The rule for postconditions therefore must be that postconditions must not be weakened by subtypes, although they can be strengthened; this enables clients of the subtype to benefit from extra features it supports.

These rules are consequences of Liskov's Behavioral Substitution Principle, which states that properties of the supertype must still be true of subtypes.  This principle is true of all inheritance hierarchies which allow subtypes to be used as elements of their supertypes.  After all, this is what a subtype means: if A is a subtype of B then every instance of A is, by definition, also an instance of B.  (This does not apply to private inheritance in C++, which doesn't imply a subtype relationship, but it does apply to public inheritance in C++, as well as to all inheritance relationships in Java, C#, and similar languages.)  The principle is true whether or not the developer uses design by contract, and writes contracts explicilty; a violation of the principle is still a bug, and a nasty one at that.  Using design by contract makes it easier to prevent such violations in the first place.

Any developer who is ignorant of Liskov's Behavioral Substitution Principle can't claim to understand object-oriented programming, and should be prevented from writing any kind of inheritance relationship!