As you are probably aware, KDE software uses the Qt library extensively. As do many other 3rd party applications.

Most of these applications use the Qt’s default text component – QLineEdit – when they need password input, because QLineEdit has a nice convenient mode where it masks the content of the text field – it shows asterisks or circles instead of the actual characters it contains.

This is a nice way to block over-the-shoulder snooping, and is a common approach to do password entry even in non-Qt software.

The underbelly

In order to see what the problem here is, we need to understand how components like QLineEdit work.

While the typed characters are not shown to the user, they are stored somewhere. Usually in a string variable as plain text (not encrypted). This means that is someone can see the contents of the process memory while the user types in the password, it will be easy to read it (problem 1).

Other problems are due to how dynamic memory works on our computers. String data is stored (usually) in the dynamic memory. When QString wants to store its data, it will reserve a chunk of memory and start filling it while the string grows (in this case, while the user is typing the password). When that chunk is filled, a new larger chunk is allocated and the data from the old chunk is copied into it. The old chunk is freed/deleted so that some future memory allocation can use the same space.

When the QLineEdit is destroyed, so is the QString variable that stores the password. But, while the buffer that QString uses to store the data is freed/deleted, its contents remain in memory until some other dynamically allocated object is created in the same memory space and overwrites the data. This is because QString does not fill its buffer with zeroes on destruction. This means that the passwords remain in memory for much longer than needed (problem 2).

Furthermore, because of string reallocation on resizing (creating a bigger chunk of memory and copying the old data into it), it is quite possible that, while the user is typing the password, that the string will be resized/reallocated at least once. This means that partial passwords (data from the buffer in the string before reallocation which is not zeroed-out) will remain in memory until something else overwrites them (problem 3).

All this memory can end up written to the HDD/SSD if the application is moved to swap by the OS (problem 4).

Small potatoes

Before you throw your computer into the fireplace, and go to the tried and tested coding systems of (c)old, we need to see how big these problems really are.

Reading passwords stored in the process memory can be done from that same process. This is usually benign because if you’re entering a password into an application, you probably trust it with said password. This can only become a problem if that application has a plugin system (with native code) and you install untrusted plugins.

This should not be a common case. Usually, privacy-aware people do not use untrusted software.

Reading memory from a separate process is a different story. This is not possible on a hardened system, but most Linux distributions tend to be developer-friendly, and this means that they allow attaching a debugger to a running process with PTRACE. And a debugger (or any process that pretends to be a debugger) can read the memory of the process it is attached to.

Regardless of whether PTRACE is enabled or not, for this to be a problem, you need to be running untrusted software that could try to extract the passwords from a process’ memory.

It is worth noting that even in the worst case scenario in which an attacker is allowed to read the memory of your processes either through a plugin or through PTRACE, finding the password (or other secret data) is like searching for a needle in a huge haystack. Normal programs tend to be filled with strings.

Furthermore, if an attacker is allowed any of this, your system is seriously compromised.

Current improvements

I’ve started this post explaining 4 different problems of using QLineEdit for password input. I’m glad to say that two of them do not exist anymore.

The latest version of Qt includes two patches (by yours truly) which remove the problem of passwords remaining in the dynamic memory of a process after the input component is destroyed. Namely, when QLineEdit is used for password input, it will fill the memory where the password was stored with zeros. Furthermore, it will preallocate a buffer for the password which is long enough so that string reallocations don’t happen for 99.99% of users.

This means that problems 2 and 3 are no longer present if you are using the latest version of Qt.

The fourth problem – the operating system moving the application that asks you for the password to the swap should also not happen in common usage. Since problems 2 and 3 are gone, the only time when the password is in memory is while you’re typing it and the OS is not going to swap an application that you are currently using.

If you don’t think this is secure enough, you can either disable the swap on your system or encrypt it.

The last problem

The last remaining problem is that the password is stored non-encrypted in memory. Luckily, thanks to the previously mentioned patches, this is a much smaller issue than it seems at first.

The password is in memory only while it is being entered/used. Which means that the window that the attacker has to try to get it is extremely narrow.

Unfortunately, this problem can not be fixed completely. If the password was kept in memory encrypted, the encryption key would need to be readily available (in memory) for the application to be able to use the password. Which means that while your password would be encrypted, the key to decrypt it wouldn’t.

So, the attacker could try to find the encryption key, then find the encrypted password, and then decrypt the password.

Now, this would be much harder to do than finding an unencrypted password. The attacker would need to find two separate things (located in different parts of the process memory) and would not be able to use any type of string analysis when searching for the chunks of memory where the secrets are stored. The encryption key would be a true random set of bytes, and the encrypted password would look like a random set of bytes – they would not look like strings at all.

Unfortunately, this is not something that can be fixed in QLineEdit. This will need a custom password edit component that uses a safe string implementation instead of QString.

To be continued…

There’s a nice post by Ryou about the projections feature of Eric Niebler’s ranges that we’re going to get in C++20.

I’ll try to provide a more general look at what projections are – not only in the context of ranges. I recommend reading Ryou’s post before or after this one for completeness.

Tables have turned

Imagine the following – you have a collection of records where each record has several fields. One example of this can be a list of files where each file has a name, size and maybe something else.

Collections like these are often presented to the user as a table which can be sorted on an arbitrary column.

By default std::sort uses operator< to compare items in the collection while sorting which is not ideal for our current problem – we want to be able to sort on an arbitrary column.

The usual solution is to use a custom comparator function that compares just the field we want to sort on (I’m going to omit namespaces for the sake of readability, and I’m not going to write pairs of iterators – just the collection name as is customary with ranges):

sort(files, [] (const auto& left, const auto& right) {
                return left.name < right.name;
            });

There is a lot of boilerplate in this snippet for a really simple operation of sorting on a specific field.

Projections allow us to specify this in a much simpler way:

sort(files, less, &file_t::name);

What this does is quite simple. It uses less-than for comparison (less), just as we have with normal std::sort but it does not call the operator< of the file_t objects in order to compare the files while sorting. Instead, it only compares the strings stored in the name member variable of those files.

That is the point of a projection – instead of an algorithm testing the value itself, it tests some representation of that value – a projection. This representation can be anything – from a member variable, to some more complex transformation.

One step back

Let’s take one step back and investigate what a projection is.

Instead of sorting, we’re going to take a look at transform. The transform algorithm with an added projection would look like this:

transform(files, destination,
          [] (auto size) { return size / 1024; }, &file_t::size);

We’re transforming a collection of files with a &file_t::size projection. This means that the transform algorithm will invoke the provided lambda with the file sizes instead of file_t objects themselves.

The transformation on each file_t value in the files collection is performed in two steps:

• First, for a file f, extract f.size
• Second, divide the result of the previous step by 1024

This is nothing more than a function composition. One function gets a file and returns its size, and the second function gets a number and divides it by 1024.

If C++ had a mechanism for function composition, we would be able to achieve the same effect like so:

transform(files, destination,
    compose_fn(
        [] (auto size) { return size / 1024; },
        &file_t::size
    ));

Note: compose_fn can be easily implemented, we’ll leave it for some other time.

Moving on from transform to all_of. We might want to check that all files are non-empty:

all_of(files, [] (auto size) { return size > 0; }, &file_t::size);

Just like in the previous example, the all_of algorithm is not going to work directly on files, but only on their sizes. For each file, the size will be read and the provided predicate called on it.

And just like in the previous example, this can be achieved by simple function composition without any projections:

all_of(files,
    compose_fn(
        [] (auto size) { return size > 0; },
        &file_t::size
    ));

Almost composition

The question that arises is whether all projections can be replaced by ordinary function composition?

From the previous two examples, it looks like the answer to this question is “yes” – the function composition allows the algorithm to “look” at an arbitrary representation of a value just like the projections do. It doesn’t matter whether this representation function is passed in as a projection and then the algorithm passes on the projected value to the lambda, or if we compose that lambda with the representation function.

The things stop being this simple when an algorithm requires a function with more than one argument like sort or accumulate do.

With normal function composition, the first function we apply can have as many arguments as we want, but since it returns only a single value, the second function needs to be unary.

For example, we might want to have a function size_in which returns a file size in some unit like kB, KiB, MB, MiB, etc. This function would have two arguments – the file we want to get the size of and the unit. We could compose this function with the previously defined lambda which checks whether the file size is greater than zero.

sort needs this to be the other way round. It needs a function of two arguments where both arguments have to be projected. The representation (projection) function needs to be unary, and the resulting function needs to be binary.

Universal projections

So, we need a to compose the functions a bit differently. The representation function should be applied to all arguments of an n-ary function before it is called.

As usual, we’re going to create a function object that stores both the projection and the main function.

template <typename Function, typename Projection>
class projecting_fn {
public:
    projecting_fn(Function function, Projection projection)
        : m_function{std::move(function)}
        , m_projection{std::move(projection)}
    {
    }

    // :::

private:
    Function m_function;
    Projection m_projection;
};

The main part is the call operator. It needs to project all the passed arguments and then call the main function with the results:

template <typename... Args>
decltype(auto) operator() (Args&&... args) const
{
    return std::invoke(
               m_function,
               std::invoke(m_projection, FWD(args))...);
}

This is quite trivial – it calls m_projection for each of the arguments (variadic template parameter pack expansion) and then calls m_function with the results. And it is not only trivial to implement, but it is also trivial for the compiler to optimize.

Now, we can use projections even with old-school algorithms from STL and in all other places where we can pass in arbitrary function objects.

To continue with the files sorting example, the following code sorts a vector of files, and then prints the files to the standard output all uppercase like we’re in 90s DOS:

    std::sort(files.begin(), files.end(),
              projecting_fn { std::less{}, &file_t::name });

    std::copy_if(
              files.cbegin(), files.cend(),
              std::ostream_iterator<std::string>(std::cout, " "),
              projecting_fn {
                  string_to_upper,
                  &file_t::name
              });

Are we there yet?

So, we have created the projected_fn function object that we can use in the situations where all function arguments need to be projected.

This works for most STL algorithms, but it fails for the coolest (and most powerful) algorithm – std::accumulate. The std::accumulate algorithm expects a function of two arguments, just like std::sort does, but it only the second argument to that function comes from the input collection. The first argument is the previously calculated accumulator.

This means that, for accumulate, we must not project all arguments – but only the last one. While this seems easier to do than projecting all arguments, the implementation is a tad more involved.

Let’s first write a helper function that checks whether we are processing the last argument or not, and if we are, it applies m_projection to it:

template <
    size_t Total,
    size_t Current,
    typename Type
    >
decltype(auto) project_impl(Type&& arg) const
{
    if constexpr (Total == Current + 1) {
        return std::invoke(m_projection, std::forward<Type>(arg));
    } else {
        return std::forward<Type>(arg);
    }
}

Note two important template parameters Total – the total number of arguments; and Current – the index of the current argument. We perform the projection only on the last argument (when Total == Current + 1).

Now we can abuse std::tuple and std::index_sequence to provide us with argument indices so that we can call the project_impl function.

template <
    typename Tuple,
    std::size_t... Idx
    >
decltype(auto) call_operator_impl(Tuple&& args,
                                  std::index_sequence<Idx...>) const
{
    return std::invoke(
            m_function,
            project_impl
                <sizeof...(Idx), Idx>
                (std::get<Idx>(std::forward<Tuple>(args)))...);
}

The call_operator_impl function gets all arguments as a tuple and an index sequence to be used to access the items in that tuple. It calls the previously defined project_impl and passes it the total number of arguments (sizeof...(Idx)), the index of the current argument (Idx) and the value of the current argument.

The call operator just needs to call this function and nothing more:

template <typename... Args>
decltype(auto) operator() (Args&&... args) const
{
    return call_operator_impl(std::make_tuple(std::forward<Args>(args)...),
                              std::index_sequence_for<Args...>());
}

With this we are ready to use projections with the std::accumulate algorithm:

std::accumulate(files.cbegin(), files.cend(), 0,
    composed_fn {
        std::plus{},
        &file_t::size
    });

Epilogue

We will have projections in C++20 for ranges, but projections can be useful outside of the ranges library, and outside of the standard library. For those situations, we can roll up our own efficient implementations.

These even have some advantages compared to the built-in projections of the ranges library. The main benefit is that they are reusable.

Also (at least for me) the increased verbosity they bring actually serves a purpose – it better communicates what the code does.

Just compare

sort(files, less, &file_t::name);
accumulate(files, 0, plus, &file_t::size);

and

sort(files, projected_fn { less, &file::name })
accumulate(files, 0, composed_fn { plus, &file_t::size });

We could also create some cooler syntax like the pipe syntax for function transformation and have syntax like this:

sort(files, ascending | on_member(&file::name))

… but that is out of the scope of this post :)

A bit more than a year ago, the KDE community decided to focus on a few goals. One of those goals (the most important one as far as I’m concerned) is to increase the users’ control over their private data.

KDE developers and users have always been a privacy-minded bunch. But due to all the fun things that have happened in the recent years, we had to switch to the next gear.

We have seen new projects like KDE Itinerary (by Volker), Plasma Vault (by yours truly), Plasma Mycroft (by Yuri and Aditya), etc. There has also been a lot of work to improve our existing projects like KMail.

Now, this post is not about any of these.

It is about a KDE Privacy developer sprint organized by Sando Knauß.

The sprint will be held in Leipzig (Germany) from 22. 3. to 26. 3. and all privacy-minded contributors are invited to join.

At the previous aKademy, one of the unformal discussions we had were about Plasma mods.

One thing I always liked about the mobile platforms like Meego (Nokia N9) and Sailfish that were/are based on Qt/QML, is that there are many available mods for them created by the community.

With QML, you basically have a lot of source files for an application (or shell) UI that get compiled when the application is run. This means that changing the look and behaviour of an application on your system is often as easy as editing a file with your favourite text editor like Kate or Vim.

Sometimes modding gets so popular that some brave community member decides to create an application that allows automatic application of these mods. This was one of my favourite things about Sailfish OS.

Mods for KDE Plasma

It was always strange to me that Plasma does not have a modders community.

Maybe it is because Plasma tends to be quite configurable by default, and mods are not as needed as on other platforms. Maybe it is that Plasma API is overwhelming for people to use it to create quick-and-dirty modifications.

Whatever the reason, I would like to see people start writing Plasma mods.

For that reason, I decided to create a repository with a few example mods – meant mostly to tackle my pet peeves in Plasma. Some of these are authored by me, some I got from the KDE forums and other places.

Folder View with the list view

I have files with quite long names. The icon view, which is the default for the Folder View applet, does not suit this setup well.

This mod hacks the applet to always think it is placed in a panel – to force it to show a vertical list of files.

Default desktop layout

I’m not a fan of keeping files on the desktop.

The main reason is that I don’t want all the files in my home directory to get shown to the audience when I connect my computer to a projector at a conference, which is now the default behaviour of Plasma.

One of the mods reverts the change introduced recently which makes the Folder View to be the default desktop layout.

Smaller volume OSD

Another thing that I’ve seen people get annoyed by is the big volume on-screen display that is the default in the Breeze look and feel.

While it looks really pretty, it hides a large portion of the screen when it is shown.

Fortunately, this is easy to fix with yet another mod.

Repository

The repository where I’ve collected these and a few other mods is located on GitHub.

The reason this is on GitHub (instead of putting it on the KDE infrastructure) is to make it clear this is not an official KDE project, nor that it is condoned by the Plasma team.

Nothing in this repository comes with warranty. Changing your system files can make your system unusable. Make sure you backup everything before trying these out.

I was considering to make the title of the post “STL algorithms considered harmful” to test my click-bait creation skills, but I decided it is better to aim for the audience interested in the topic of the post instead of getting readers who just want to argue about my outrageous claims.

This way, I can assume that you care about algorithms, algorithm complexity and writing the best software that you can.

Algorithms

One of the advices commonly heard in the modern C++ community is to use the algorithms provided by the standard library if you want to make your program safer, faster, more expressive, etc. This is the advice I also try to popularize – in my book, talks, workshops… everywhere I have the audience to do so.

While it is true that whenever we want to write a for loop to solve a problem we have, we should first consider whether there is a way to solve that problem with the standard (or boost) algorithms, we should not do it blindly.

We still need to know how those algorithms are implemented, what are their requirements and guarantees, and what is their space and time complexity.

Usually, if we have a problem that perfectly matches the requirements of an STL algorithm so that we can apply it directly, that algorithm will be the most effective solution.

The problem can arise when we have to prepare the data in some way prior to applying the algorithm.

Set intersection

Imagine we’re writing a tool for C++ developers to give advisories of replacing default-captures ([=] and [&]) in lambdas with an explicit list of captured variables.

std::partition(begin(elements), end(elements),
    [=] (auto element) {
    ^~~ - being implicit is uncool, replace with [threshold]
        return element > threshold;
    });

While parsing the file, we would need to keep a collection containing the variables from current and surrounding scopes, and when we encounter a lambda with a default-capture we need to see which variables it uses.

This gives us two sets – one set containing the variables from the surrounding scopes, and one set containing the variables used in the lambda body.

The capture list we should propose as a replacement should be intersection of those two sets (lambda can use global variables which do not need to be captured, and not all variables from the surrounding scopes are used in the lambda).

And, if we need intersection, we can use the std::set_intersection algorithm.

This algorithm is quite beautiful in its simplicity. It takes two sorted collections, and goes through them in parallel from start to end:

• If the current item in the first collection is the same as the current item in the second collection, it gets added to the result the algorithm just moves on to the next item in both collections;
• If the current item in the first collection is less than the current item in the second collection, the algorithm just skips the current item in the first collection;
• If the current item in the first collection is greater than the current item in the second collection, the algorithm just skips the current item in the second collection.

With each iteration at least one element (from the first or the second input collection) is skipped – therefore, the algorithm complexity will be linear – O(m + n), where m is the number of elements in the first collection, and n the number of elements in the second collection.

Simple and efficient. As long as the input collections are sorted.

Sorting

The problem is what to do when collections are not sorted in advance.

In the previous example, it would be prudent to store the variables from the surrounding scopes in a stack-like structure so that the parser can efficiently add new ones when it enters a new scope, and remove the variables from the current scope when it leaves the current scope.

This means that the variables will not be sorted by name and that we can not use std::set_intersection directly to operate on them. Similarly, tracking the variables in the lambda body is very likely not going to keep them sorted.

Since std::set_intersection works only on sorted collections, it is a common pattern I’ve seen in many projects to first sort the collections, and then call the std::set_intersection algorithm.

Skipping the fact that sorting the variables stack in our example would destroy the purpose of the stack we defined, the intersection algorithm for unordered collections would look like this:

template <typename InputIt1, typename InputIt2, typename OutputIt>
auto unordered_intersection_1(InputIt1 first1, InputIt1 last1,
                              InputIt2 first2, InputIt2 last2,
                              OutputIt dest)
{
    std::sort(first1, last1);
    std::sort(first2, last2);
    return std::set_intersection(first1, last1, first2, last2, dest);
}

What is the complexity of the whole algorithm?

Sorting takes quasilinear time, which makes the total complexity of this approach O(n log n + m log m + n + m).

Sort less

Can we skip sorting?

If both collections are unordered, we would need to traverse the second collection for each element in the first one – to check whether it needs to be put into the resulting set. Although this approach is not that uncommon in real-world projects, it is even worse than the previous one – its complexity is O(n * m).

Instead sorting everything, or sorting nothing, we can be Zen and take the Middle Path – sort only one collection.

If only one collection is sorted, we will have to iterate through the unsorted one value by value and check whether that value exists in the sorted collection for which we can use binary search.

The time complexity for this will be O(n log n) for sorting the first collection, and O (m log n) for iteration and checking. In total, we have O((n + m) log n) complexity.

If we decided to sort the second collection instead of the first, the complexity would be O((n + m) log m).

In order to be as efficient as possible, we will always sort the collection that has fewer elements thus making the final complexity for our algorithm ((m + n) log (min(m, n)).

The implementation would look like this:

template <typename InputIt1, typename InputIt2, typename OutputIt>
auto unordered_intersection_2(InputIt1 first1, InputIt1 last1,
                              InputIt2 first2, InputIt2 last2,
                              OutputIt dest)
{
    const auto size1 = std::distance(first1, last1);
    const auto size2 = std::distance(first2, last2);

    if (size1 > size2) {
        unordered_intersection_2(first2, last2, first1, last1, dest);
        return;
    }

    std::sort(first1, last1);

    return std::copy_if(first2, last2, dest,
        [&] (auto&& value) {
            return std::binary_search(first1, last1, FWD(value));
        });
}

In our example of lambda captures, the collection that we’d want to sort is usually going to be the collection of variables used in the lambda as it is most likely going to be smaller than a list of all variables from all surrounding scopes.

Hashing

The last option is to build a std::unordered_set (unordered, hash-based set implementation) from the smaller collection instead of sorting it. This will make lookups O(1) on average, but the construction of std::unordered_set will take time. Construction can be between O(n) and O(n*n) which can be a problem.

template <typename InputIt1, typename InputIt2, typename OutputIt>
void unordered_intersection_3(InputIt1 first1, InputIt1 last1,
                              InputIt2 first2, InputIt2 last2,
                              OutputIt dest)
{
    const auto size1 = std::distance(first1, last1);
    const auto size2 = std::distance(first2, last2);

    if (size1 > size2) {
        unordered_intersection_3(first2, last2, first1, last1, dest);
        return;
    }

    std::unordered_set<int> test_set(first1, last1);

    return std::copy_if(first2, last2, dest,
        [&] (auto&& value) {
            return test_set.count(FWD(value));
        });
}

The hashing approach would be the absolute winner for the case where we want to calculate intersections of several sets with a single predefined small set. That is, we have a set A, sets B₁, B₂… and we want to calculate A ∩ B₁, A ∩ B₂…

In this case, we could ignore the complexity of the std::unordered_set construction, and the complexity of calculating each intersection would be linear – O(m), where m is the number of elements in the second collection.

Benchmark

While it is always useful to check the algorithm complexity, it is prudent also to benchmark different approaches in cases like these. Especially when choosing between the last two approaches where we pit binary search against hash-based sets.

In my basic benchmarks, the first option where both collections have to be sorted was always the slowest.

Sorting the shorter collection was slightly better than using std::unordered_set, but not much.

Both the second and the third approach were slightly faster than the first in the case when both collections had the same number of elements, and were significantly faster (6x) when one collection had 1000x less elements than the other.