“make deb-pkg” broken

Last time when I hacked the Linux kernel on Ubuntu, it was 4.4 on LTS 14.04. Time flies. Now I need to hack the kernel 4.13 again on LTS 16.04, and find the kernel build broken. It is fine that we could not have a stable kernel API since at least the ABI is stable. But what about kernel build?

1. “make deb-pkg” broken

This used to be my way to build a kernel on Ubuntu. If something wrong happens and stops the build, just fix the error and repeat the command again — it was incremental build. But now it is broken, as it launches “make clean” by default. Why? Because it needs to generate a source tar at first, which requires a “clean” to exclude all build artifacts[1]. Instead, use “make bindeb-pkg“.

2. VirtualBox build broken

I have no idea when Ubuntu decided to include VirtualBox guest/drivers into the kernel tree, but it is broken, because the source directory structure is different from the ones used by the makefiles. An “ln” based workaround is available[2], although I just hacked those makefiles to fix errors.

[1] https://unix.stackexchange.com/questions/368864/re-building-linux-kernel-without-clean
[2] http://technote.thispage.me/index.php/2016/12/20/ubuntu-16-04-kernel-compile-on-default-setting/

Posted in Linux Distro | Tagged , , | Leave a comment

Running Multics on Linux (Fedora 27)

This post follows the “Multics Simulator Instructions”[1] (with some tweaks) to setup Multics simulator dps8m and run Multics on my Fedora 27. Other Linux distro (Ubuntu/Debian/Raspbian) may need some changes but basically work the same way. Experience the cutting-edge secure operating system made on 1960s by yourself!


1. Install deps – libuv

While libuv can be built from source[2], it would be more easier to install the library using your package manager. For Fedora 27:

dnf install libuv libuv-devel

2. Build the simulator – dps8

Once libuv and its header files are installed, go ahead to build the simulator following the instructions[2]:

git clone git://git.code.sf.net/p/dps8m/code dps8m-code
cd dps8m-code
git checkout R1.0

Once the build is done, the dps8 binary can be found under dps8m-code/src/dps8.

3. Run dps8

mkdir -p $HOME/multics/linux
cp $HOME/dps8m-code/src/dps8/dps8 $HOME/multics/linux
cp $HOME/dps8m-code/src/dps8/Devices.txt $HOME/multics/linux

This should start the simulator. Type “quit” to exit the simulator:

[daveti@daveti linux]$ ./dps8
DPS8/M emulator (git b7a50ffc)
Production build
DPS8M system session id is 18555
Please register your system at https://ringzero.wikidot.com/wiki:register
or create the file ‘serial.txt’ containing the line ‘sn: 0’.
FNP telnet server port set to 6180

DPS8M simulator V4.0-0 Beta git commit id: c420925a
sim> quit
[daveti@daveti linux]$

4. Run Multics

Download the QuickStart disk image, unzip it, and mv/rename disk image directory as multics/qs:

wget https://s3.amazonaws.com/eswenson-multics/public/releases/MR12.6f/QuickStart_MR12.6f.zip
unzip $HOME/QuickStart*.zip
mv $HOME/QuickStart_MR12.6f $HOME/multics/qs
cd $HOME/multics/qs
../linux/dps8 MR12.6f_boot.ini

The whole booting process takes a while, but you should be able to see something below if Multics starts correctly:

[daveti@daveti qs]$ ../linux/dps8 MR12.6f_boot.ini
DPS8/M emulator (git b7a50ffc)
Production build
DPS8M system session id is 18555
Please register your system at https://ringzero.wikidot.com/wiki:register
or create the file ‘serial.txt’ containing the line ‘sn: 0’.
FNP telnet server port set to 6180

DPS8M simulator V4.0-0 Beta git commit id: c420925a
TAPE: unit is read only
bootload_0: Booting system MR12.6f generated 01/09/17 1119.1 pst Mon.
0426.6 announce_chwm: 428. pages used of 512. in wired environment.
0426.6 announce_chwm: 706. words used of 1024. in int_unpaged_page_tables.
find_rpv_subsystem: Enter RPV data: M-> [auto-input] rpv a11 ipc 3381 0a

0426.7 load_mst: 946. out of 1048. pages used in disk mst area.
bce (early) 0426.7: M-> [auto-input] bce

Multics Y2K. System was last shudown/ESD at:
Wednesday, January 17, 2018 17:07:31 pst
Current system time is: Wednesday, January 17, 2018 20:26:43 pst.
Is this correct? M-> [auto-input] yes

The current time is more than the supplied boot_delta hours beyond the
unmounted time recorded in the RPV label. Is this correct? M-> [auto-input] yes

bce (boot) 2026.7: M-> [auto-input] yes

bce: Unrecognizable request. Type lr for a list of requests.
bce (boot) 2026.7: M-> [auto-input] boot star

Multics MR12.6f – 01/17/18 2027.0 pst Wed
2027.0 Loading FNP d, >user_dir_dir>SysAdmin>a>mcs.7.6c>site_mcs 7.6c
Received BOOTLOAD command…
listening to 6180
2027.0 FNP d loaded successfully

scavenge_vol: No volumes found
2027 as as_init_: Multics MR12.6f; Answering Service 17.0
2027 as LOGIN IO.SysDaemon dmn cord (create)
2027 as LOGIN Backup.SysDaemon dmn bk (create)
2027 as LOGIN IO.SysDaemon dmn prta (create)
2027 as LOGIN Utility.SysDaemon dmn ut (create)
2027 as LOGIN Volume_Dumper.Daemon dmn vinc (create)
fnpuv_open_slave 3.31
listening on port 6131
2027 as as_mcs_mpx_: Load signalled for FNP d.

2027 cord Enter command: coordinator, driver, or logout:
–> cord
2027 bk
2027 prta Enter command: coordinator, driver, or logout:
–> prta
2027 ut copy_dump: Attempt to re-copy an invalid dump.
2027 bk r 20:27 0.446 37
2027 bk
–> bk
2027 vinc
2027 vinc r 20:27 0.450 25
2027 vinc
–> vinc
2027 as sc_admin_command_: Utility.SysDaemon.z: delete_old_pdds
2027 ut send_admin_command: Execution started …
2027 ut completed.
2027 ut monitor_quota: The requested action was not performed.
2027 ut The quota of >dumps is 0, a record limit needs to be specified.
2027 ut
2027 ut Records Left % VTOCEs Left % PB/PD LV Name
2027 ut
2027 ut 166172 100086 60 42218 34130 81 pb root
2027 ut
2027 ut r 20:27 2.481 498
2027 ut
–> ut
2027.2 RCP: Attached tapa_00 for Utility.SysDaemon.z
2027.2 RCP: Detached tapa_00 from Utility.SysDaemon.z
2027.2 RCP: Attached rdra for Utility.SysDaemon.z
2027.2 RCP: Detached rdra from Utility.SysDaemon.z
2027.2 RCP: Attached puna for Utility.SysDaemon.z
2027.2 RCP: Detached puna from Utility.SysDaemon.z
2027.2 RCP: Attached prta for Utility.SysDaemon.z
2027.2 RCP: Detached prta from Utility.SysDaemon.z

Once we have Multics running, we can try to login the system with the help of telnet and the login command in a new terminal. For the first-time login as “Repair” user, the default passwd is “repair”. A new passwd is asked immediately by the system used to replace the old passwd. NOTE: you need to create a new passwd everytime logging into the system! Once logged in, type simple “who” command, and then “logout”:

[daveti@daveti ~]$ telnet localhost 6180
Trying ::1…
telnet: connect to address ::1: Connection refused
Connected to localhost.
Escape character is ‘^]’.
HSLA Port (d.h000,d.h001,d.h002,d.h003,d.h004,d.h005,d.h006,d.h007,d.h008,d.h009,d.h010,d.h011,d.h012,d.h013,d.h014,d.h015,d.h016,d.h017,d.h018,d.h019,d.h020,d.h021,d.h022,d.h023,d.h024,d.h025,d.h026,d.h027,d.h028,d.h029)?
Attached to line d.h000

Multics MR12.6f: Installation and location (Channel d.h000)
Load = 5.0 out of 90.0 units: users = 5, 01/17/18 2035.3 pst Wed

login Repair -cpw
New Password:
New Password Again:
Password changed.
You are protected from preemption.
Repair.SysAdmin logged in 01/17/18 2035.6 pst Wed from ASCII terminal “none”.

New messages in message_of_the_day:

Welcome to the Multics System.

print_motd: Created >user_dir_dir>SysAdmin>Repair>Repair.value.
r 20:35 0.469 33

who -a -lg

Multics MR12.6f; Installation and location
Load = 6.0 out of 90.0 units; users = 6, 1 interactive, 5 daemons.
Absentee users = 0 background; Max background absentee users = 3
System up since 01/17/18 2027.0 pst Wed
Last shutdown was at 01/17/18 1707.4 pst Wed

Login at TTY Load User ID

01/17/18 20:27 cord 1.0 IO.SysDaemon
20:27 bk 1.0 Backup.SysDaemon
20:27 prta 1.0 IO.SysDaemon
20:27 ut 1.0 Utility.SysDaemon
20:27 vinc 1.0 Volume_Dumper.Daemon
20:35 none 1.0 Repair.SysAdmin

r 20:36 0.102 3

Repair.SysAdmin logged out 01/17/18 2036.8 pst Wed
CPU usage 1 sec, memory usage 0.1 units, cost $0.07.
Multics has disconnected you
Connection closed by foreign host.

Meanwhile, you should be able to see the logging information on the Multics ternimal:

<>CONNECT to d.h000
2035 as LOGIN Repair.SysAdmin int d.h000 (create)
2036 as LOGOUT Repair.SysAdmin.a int d.h000 0: 0 $0.07 (logo)

5. Multics 101

All commands can be found at [3]. Go ahead to try “ls”, “who”, “date”, “time”, and etc. There is also an Emacs available (no Vi apparently). The command mapping between Multics and Linux may also be useful to have a quick understanding of Multics commands[4]. For instance, if you want to take a look at the source file of Multics (HINT: neither B nor C):

cwd >ldd>mcs>source
pr ic_sampler.map355

(Another Hint: Ctrl-C can be your friend~)

6. Now what?

Once we “logout”, it is time to learn how to quit Multics (gracefully). Yes, you need to learn how to quit – take a look at [5] and use 5 ESCs and 5 commands to shutdown Multics:

M-> logout * * *


2110 as LOGOUT IO.SysDaemon.z dmn cord 0: 0 $0.03 (looc)
2110 as LOGOUT Backup.SysDaemon.z dmn bk 0: 0 $0.04 (looc)
2110 as LOGOUT IO.SysDaemon.z dmn prta 0: 0 $0.03 (looc)
2110 as LOGOUT Utility.SysDaemon.z dmn ut 0: 3 $1.90 (looc)
2110 as LOGOUT Volume_Dumper.Daemon.z dmn vinc 0: 0 $0.04 (looc)
M-> shut

2110 as act_ctl_: shutdown, 8 0.05 0.05 0.00 0.02 0:3:21 $16.99
2110.9 shutdown complete
DBG(16336227444863)> ERR ERR: Need status register data format
DBG(16336227444911)> ERR ERR: doPayloadChan expected IDCW 10 (12)
bce (boot) 2110.9: M-> die

Do you really wish bce to die? M-> yes

BCE DIS causes CPU halt

simCycles = 16336308761570

cpuCycles = 698896257
Timer runout faults = 21587
Derail faults = 1
Lockup faults = 65
Connect faults = 7242
Illegal procedure faults = 5
Directed fault 0 faults = 754
Directed fault 1 faults = 6926
Access violation faults = 370
Fault tag 2 faults = 3052

Halt, IC: 000012 (000000000000)
sim> quit
[daveti@daveti qs]$


[1] http://multicians.org/sim-inst.html
[2] http://ringzero.wikidot.com/r1-build-from-git
[3] http://multicians.org/multics-commands.html
[4] http://swenson.org/multics_wiki/index.php?title=Linux-to-Multics_Command_Mapping
[5] http://multicians.org/sim-inst-linux.html

Posted in OS, Security | Tagged , , , | 1 Comment

Some notes on the Monotonic Counter in Intel SGX and ME

SGX sealing is vulnerable to rollback attacks as the enclave is not able to tell if the sealed data is the latest or a old copy. To mitigate this attack, monotonic counter (MC) has been introduced in Intel SGX SDK 1.8. This post looks into some implementation details inside Intel SGX SDK.

1. sgx_create_monotonic_counter[1]

Look at the description of this API, two things show up – first, the counter creation involves non-volatile memory (NVM) writing; second, limited number of MCs can be created per enclave due to the quota. Apparently, unlike the older version of Intel SGX SDK, where MC was only available in the simulation mode, the MC here is based on real NVM, which also seems to have limited capacity. Let’s go deeper.

2. PSE (Platform Service/Security Enclave?)

The MC creation essentially calls sgx_create_monotonic_counter_ex[2] inside SDK. This function builds two pse_message_t messages for the request and reply, which are both passed to crypt_invoke. The crypt_invoke function establishes a PSE session (secure and authenticated channel) with aesmd, encrypts the request using the shared secret, and calls uae_invoke_service with both the request and reply passed, which eventually calls invoke_service_ocall[3] in the PSE provided by PSW other than the SDK.

3. OAL (OS Abstraction Layer?)

The PSE request and reply are then delivered to oal_invoke_service[4], which essentially transforms the PSE messages into AEInvokeServiceRequest and AEInvokeServiceResponse, and sends the AE messages to aesmd via UNIX socket ‘/var/run/aesmd/aesm.socket’. This MC creation request will then be handled by PSE_MC_SERVICE as a PSE_MC_CREATE command[1]

4. PSE_OP (PSE OPeration?)

The service handler table defined in pse_op.cpp[5] lists all the MC related command PSE_MC_SERVICE supports:

static const struct service_handler_t
    uint16_t  service_id;
    uint16_t  service_cmd;
    uint16_t  req_size;
    uint16_t  resp_size;
    srv_pfn_t srv_pfn;
} service_handler[] = {
    {PSE_MC_SERVICE, PSE_MC_CREATE, sizeof(pse_mc_create_req_t), sizeof(pse_mc_create_resp_t), pse_mc_create},
    {PSE_MC_SERVICE, PSE_MC_READ,   sizeof(pse_mc_read_req_t),   sizeof(pse_mc_read_resp_t),   pse_mc_read  },
    {PSE_MC_SERVICE, PSE_MC_INC,    sizeof(pse_mc_inc_req_t),    sizeof(pse_mc_inc_resp_t),    pse_mc_inc   },
    {PSE_MC_SERVICE, PSE_MC_DEL,    sizeof(pse_mc_del_req_t),    sizeof(pse_mc_del_resp_t),    pse_mc_del   },
    {PSE_TRUSTED_TIME_SERVICE, PSE_TIMER_READ,   sizeof(pse_timer_read_req_t), sizeof(pse_timer_read_resp_t), pse_read_timer},

And pse_mc_create is our target handler.

5. VMC (Virtual Monotonic Counter?)

Now we are into create_vmc[6], described as “create a VMC in SQLite Database and return UUID of the VMC to the caller”. Huh, so the MC is essentially an entry in a SQLite DB. So how could a SQLite DB defend against rollback attacks given that it is just a normal file on the disk? Hang on. Let’s continue. When this is the first MC creation request ever happend, we need to create the VMC DB first, via initialize_sqlite_database_file[7]. This very first thing it does is to call read_rpdata[8]. As its file name implies, the SQLite DB accesses hardware (NV) to get the hash of the DB at certain epoch, which is essentailly a HW MC. We are getting close to the real HW…

6. PSDA_Service[9]

This file contains all functions used by the VMC SQLite DB to create/delete/update HW MC in the so-far-unknown HW via invoke_psda_service. An ephemeral session is established in the function to provide secure and authenticated communication with the mystery HW, through psda_invoke_service_ocall[10], and eventually psda_invoke_service[11].

7. Intel ME

Just looking at the psda_invoke_service is really insightful:

    JVM_COMM_BUFFER commBuf;
    commBuf.TxBuf->buffer = psda_req_msg;
    commBuf.TxBuf->length = psda_req_msg_size;
    commBuf.RxBuf->buffer = psda_resp_msg;
    commBuf.RxBuf->length = psda_resp_msg_size;
    int response_code;
    ae_error_t ret;

    ret = PSDAService::instance().send_and_recv(

JVM? JHI? Finally, we have reached the dark side of the MC. Somehow some Java shit involves in communicating with the secret HW[13] — Yes, it is Intel ME! JHI stands for Java Host Interface, which is used to install Java applets into Dynamic Application Loader (DAL) firmware (inside ME) and communicate with them[12]. Yes, the SGX MC is essentially implemented in ME as a Java applet called “PSDA”!

8. PSDA.dalp

PSDAService::install_psda[14] installs the psda applet into ME using JHI. Not surprisingly, the source code for psda is not available. Instead, the download_prebuilt.sh script is used to download the applet binary directly, since it needs to signed by Intel — Right! Intel does not want anyone to install any applet into ME, for security reasons!!! After running the download script, PSDA.dalp will appear under psw/ae/data/prebuilt. It is encoded as Base64:


Copying out the Base64 encoded applet and running decoding, we have a chance to peek into the implementation of the applet:

                                             com.intel.uicom.intel.util	java.langPlatformServiceDalAppletBytesArrayInputStreamBytesArrayOutputStream
                                  CodeWrapper	Constants#Constants$CSE_PLATFORM_CAPABILITIES!Constants$CSE_SERVICE_RESP_STATUS!Constants$EPHEMERAL_SESSION_STATEConstants$LT_SESSION_STATEConstants$MEDIAPATH_IDonstants$PSDA_COMMARPDataServiceServiceFactoryServiceMessageFactoryTrustedTimeServiceServiceHandlerPSDACommonMessage$PSDA_SERVICE_ID
EphSessionEphSessionManager	LTSessionLTSessionManager
                                                                     DALApiProxy	DebugUtil	FlashUtilSGXMonotonicCounterProxyCryptoException	EpidAlgExHashAlgIllegalParameterExceptionNotSupportedExceptionOperationFailedExceptionRandom
UtilExceptionimeExceptionObjectString                 IntelAppletSEMonotonicCounter
StringBuilder   Throwable            StringBuffer
pairing_sk	payloadIv
timerEpochversionwrappedEncryptKeabandonSessionclearcreateServiceCommandcreateServiceMessage	deriveIDseraseAllFlashData
                                                                                                             printreadFlashDatareadInreadLongonprocessLTSessioreadByte	readBytes
readObjectreadPairingCounter	readShortresetresponseWithMessageseekset!setFlashStoragePropertyAntiReplay
                                                                                                          setResponse	setSeqNumsetTimesigmaSetPropertyAppendSVNsizestartEphemeralSessionstartLongTermSession
               updateRPData	writeByte
writeByteswriteFlashData_0writeFlashData_writeInt	writeLong

9. Intel ME Again

Although we only looked at the MC creation in SGX, this post has been long enough. Last thing about SGX MC is still about Intel ME. If you have seen dmesg like “Device doesn’t have valid ME Interface”, and neither /dev/mei nor /dev/mei0 is created, it is very likely that you are running a server platform with a different ME firmware (SPS) comparing to desktops/laptops[15], and the corresponding DAL firmware is not available in SPS. This means SGX MC is NOT available for servers!!! Well, I guess this does not really matter as people are in a rush to disable ME anyway… On the other hand, implementing SGX MC using ME seems to be the most reasonable choice (at least, we are still inside the CPU package), although this makes “SGX defends against ME attacks” statement in vain.


[1] https://software.intel.com/en-us/node/709160
[2] https://github.com/01org/linux-sgx/blob/master/sdk/tae_service/tae_service.cpp
[3] https://github.com/01org/linux-sgx/blob/master/psw/uae_service/sgx_uae_service.cpp
[4] https://github.com/01org/linux-sgx/blob/master/psw/uae_service/uae_wrapper/src/tae_ocall_api.cpp
[5] https://github.com/01org/linux-sgx/blob/master/psw/ae/pse/pse_op/pse_op.cpp
[6] https://github.com/01org/linux-sgx/blob/master/psw/ae/pse/pse_op/monotonic_counter_database_sqlite_rpdb.cpp
[7] https://github.com/01org/linux-sgx/blob/master/psw/ae/pse/pse_op/monotonic_counter_database_sqlite_bin_hash_tree_utility.cpp
[8] https://github.com/01org/linux-sgx/blob/master/psw/ae/pse/pse_op/monotonic_counter_database_sqlite_access_hw_mc.cpp
[9] https://github.com/01org/linux-sgx/blob/master/psw/ae/pse/pse_op/psda_service.cpp
[10] https://github.com/01org/linux-sgx/blob/master/psw/ae/aesm_service/source/pse_op/pse_op_psda_ocall.cpp
[11] https://github.com/01org/linux-sgx/blob/master/psw/ae/aesm_service/source/pse_op/PSEClass.cpp
[12] https://github.com/intel/dynamic-application-loader-host-interface
[13] https://www.slideshare.net/codeblue_jp/igor-skochinsky-enpub
[14] https://github.com/01org/linux-sgx/blob/master/psw/ae/aesm_service/source/pse_op/PSDAService.cpp
[15] https://software.intel.com/en-us/forums/intel-business-client-software-development/topic/696357

Posted in Security | Tagged , , , | 12 Comments

Why list and charlist are confusing in Elixir

This post talks about list and charlist in Elixir, and discusses one specific issue in Elixir.

Let’s look at the confusing thing in Elixir:

iex(2)> a = [7]
iex(3)> b = ‘\a’
iex(4)> a == b
iex(5)> is_list(a)
iex(6)> is_list(b)

First, a list is shown as a charlist in iex; second, (without surprise if we believe in iex), the charlist equals the list; last, both the list and the charlist are lists.

Why? Because charlist in represented as a list with code point(s) inside, and those encoding scheme is UTF-8 (rather than UTF-16 in Erlang). To convince yourself:

iex(7)> Enum.map(0..255, fn x -> [x] end)
[[0], [1], [2], [3], [4], [5], [6], ‘\a’, ‘\b’, ‘\t’, ‘\n’, ‘\v’, ‘\f’, ‘\r’,
[14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26],
‘\e’, [28], [29], [30], [31], ‘ ‘, ‘!’, ‘”‘, ‘#’, ‘$’, ‘%’, ‘&’, ‘\”, ‘(‘,
‘)’, ‘*’, ‘+’, ‘,’, ‘-‘, ‘.’, ‘/’, ‘0’, ‘1’, …]

Looks familiar? Yes, those are ASCII codes. So the conclusion seems to be that list and charlist are the same in Elixir. Well, this is mostly right, as we have seen, but not exactly right. Run the file below to inspect into list and charlist internal using pry:

require IEx

value_list = [7]
value_list2 = [1]
value_char = '\a'


daveti@Daves-MacBook-Pro:~/elixir/list_issue$ iex list_issue.exs
Erlang/OTP 20 [erts-9.0] [64-bit] [smp:4:4] [ds:4:4:10] [async-threads:10] [hipe] [kernel-poll:false] [dtrace]

Request to pry #PID<0.83.0> at list_issue.exs:7

5: value_char = ‘\a’
7: IEx.pry

Allow? [Yn]
Interactive Elixir (1.5.1) – press Ctrl+C to exit (type h() ENTER for help)
pry(1)> i value_list
Data type
This is a list of integers that is printed as a sequence of characters
delimited by single quotes because all the integers in it represent valid
ASCII characters. Conventionally, such lists of integers are referred to as
“charlists” (more precisely, a charlist is a list of Unicode codepoints,
and ASCII is a subset of Unicode).
Raw representation
Reference modules
Implemented protocols
IEx.Info, Collectable, Enumerable, Inspect, List.Chars, String.Chars
pry(3)> i value_list2
Data type
Reference modules
Implemented protocols
IEx.Info, Collectable, Enumerable, Inspect, List.Chars, String.Chars
pry(5)> i value_char
Data type
This is a list of integers that is printed as a sequence of characters
delimited by single quotes because all the integers in it represent valid
ASCII characters. Conventionally, such lists of integers are referred to as
“charlists” (more precisely, a charlist is a list of Unicode codepoints,
and ASCII is a subset of Unicode).
Raw representation
Reference modules
Implemented protocols
IEx.Info, Collectable, Enumerable, Inspect, List.Chars, String.Chars

Now you see the difference between list and charlist. Both have data type list, which explains why they are equivalent. Moreover, when the numbers inside the list could be interpreted as valid ASCII code points, Elixir shows it as a charlist rather than a list, although the raw presentation is always a list.

Why this is confusing? Let’s say you wanna print out a list, e.g., [7], but what Elixir displays is ‘\a’. Although it does not affect the internal computation, e.g., map, this display issue is really annoying and confusing. In this case, Erlang seems doing sane:

Eshell V9.0 (abort with ^G)
1> [7].
2> ‘\a’.
3> [7] == ‘\a’.

Posted in Programming | Tagged , , , , | Leave a comment

A PoC of DoS attack in Elixir Actor Model

The naive way of using the Actor model in Elixir is using “receive” in a loop, which is then “spawn”d as a Erlang process. Unfortunately, a potential DoS attack could happen if the pattern matching is not coded carefully with security in mind. This post looks into this potential vulnerability, and provides a PoC implementation.

A typical “receive” block in Elixir provides different pattern matchings, like below:

receive do
      {sender_pid, {:msg, _msg}} ->
        send(sender_pid, {:ok, "gotcha"})
      _ ->
        IO.puts "WTF"

Following the same order of matchings, the message goes through each matching one by one till finding a match. Otherwise, “_” (matching all) catchs whatever received. While this defensive matching all seems optional, it is vital to the security of the Erlang VM. As turns out, the message would stay in the mailbox forever, if no matching is able to “catch” the message. The potential result is DoS attack, caused by OOM (out of memory) of the mailbox.

To observe this potential DoS attack, please download the PoC (https://github.com/daveti/edos). As shown below, unmatched messages keep accumulating in the mailbox (message queue) when running edos:

msg 24645 sent
worker msg queue len {:message_queue_len, 24645}
msg 24646 sent
worker msg queue len {:message_queue_len, 24646}
msg 24647 sent
worker msg queue len {:message_queue_len, 24647}
msg 24648 sent

“top” also shows the memory usage (of beam.smp) keep increasing as more messages are sent to the mailbox. This DoS could turn into DDoS easily in a distributed environment.

As usual, Elixir compiler does not complain about this during the compilation time, although it would be really useful for the compiler to give some warnings. Nothing is gonna happen in runtime as well, except the memory consumption of the mailbox, which is “invisible” to the user. Even worse, dialyxir also reports nothing regarding this potential issue.

One more thing needs to verify is whether a GenServer implementation without handle_info/2 would also cause DoS in the mailbox. I suspect it the same as above.

Posted in Programming, Security, Static Code Analysis | Tagged , , , , | Leave a comment

A pitfall of GenServer programming in Elixir

OTP as a programming platform/framework, empowers not only Erlang, but also Elixir. This post looks into a pitfall when programming GenServer in Elixir, and provides a potential solution.

All callbacks in the GenServer behavior have a limited and pre-defined possible return values. Presumbly, one should pick up the desired return value from valid ones. One example for handle_call/3 looks like below:

{:reply, reply, new_state}

But what if we screw the return value, e.g., by mistakes like below,

{:reply, reply, :ok, new_state}

where atom :ok is added as an extra parameter of the return value. One would hope the Elixir compiler would catch this simple mistake. Nevertheless, neither mix compile or mix escript.build would report this bug. And yes, this bug will be triggered when handle_call/3 is called with a “Bad Argument” exception thrown out.

While “let it crash” and “unit testing” may be good reasons for Elixir compiler to treat this bug as a runtime one rather than a compiling one, this also means this simple bug won’t be discovered util deployment if unit testing is not covered properly. And once it happens, it keeps crashing “thanks” to the fault-tolerant feature using Supervisor…

Without changes in the Elixir compiler, it is still possible to detect this bug, using dialyxir (yes, Elixir version of dialyzer for sure). “mix dialyxir” shows the detection of this bug:

done in 0m1.52s
lib/dig.ex:9: The inferred return type of handle_call/3 ({‘reply’,{‘ok’,{_,_,_,_,_}},’ok’,#{‘__struct__’:=’Elixir.Digdb’, ‘node’:=_, ‘prefix’:=_, ‘remote’:=_, ‘unit_base’:=_, ‘unit_range’:=_, ‘worker_idx’:=_, ‘zero_num’:=_}}) has nothing in common with {‘noreply’,_} | {‘noreply’,_,’hibernate’ | ‘infinity’ | non_neg_integer()} | {‘reply’,_,_} | {‘stop’,_,_} | {‘reply’,_,_,’hibernate’ | ‘infinity’ | non_neg_integer()} | {‘stop’,_,_,_}, which is the expected return type for the callback of the ‘Elixir.GenServer’ behaviour
done (warnings were emitted)

Posted in Programming, Static Code Analysis | Tagged , , , , | Leave a comment

Pitfalls in negative indexing in C

Negative indexing in C, such as a[-1], is legit, although rarely used. There are reasons (pitfalls) why negative indexing is not recommended. This post discusses these pitfalls when using negative indexing (for fun).

1. Negative indexing within the bound

#include <stdio.h>
#include <string.h>

int main()
	int a[10];
	int *p;
	int i;

	for (i = 0; i < 10; i++)
		a[i] = 0x12345678;
	p = &a[9];

	for (i = 0; i < 10; i++) {
		printf("a[%d]=0x%x, %p\n", i, a[i], &a[i]);
		printf("p[-%d]=0x%x, %p\n", i, p[-i], &p[-i]);

	return 0;

In the code above, we let pointer p pointing to the end of array a, and print out each element in a using negative indexing with the help of p.

[daveti@daveti c]$ ./negidx0
a[0]=0x12345678, 0x7ffd50edad40
p[-0]=0x12345678, 0x7ffd50edad64
a[1]=0x12345678, 0x7ffd50edad44
p[-1]=0x12345678, 0x7ffd50edad60
a[2]=0x12345678, 0x7ffd50edad48
p[-2]=0x12345678, 0x7ffd50edad5c
a[3]=0x12345678, 0x7ffd50edad4c
p[-3]=0x12345678, 0x7ffd50edad58
a[4]=0x12345678, 0x7ffd50edad50
p[-4]=0x12345678, 0x7ffd50edad54
a[5]=0x12345678, 0x7ffd50edad54
p[-5]=0x12345678, 0x7ffd50edad50
a[6]=0x12345678, 0x7ffd50edad58
p[-6]=0x12345678, 0x7ffd50edad4c
a[7]=0x12345678, 0x7ffd50edad5c
p[-7]=0x12345678, 0x7ffd50edad48
a[8]=0x12345678, 0x7ffd50edad60
p[-8]=0x12345678, 0x7ffd50edad44
a[9]=0x12345678, 0x7ffd50edad64
p[-9]=0x12345678, 0x7ffd50edad40

The output proves what we would expect. Subcriptor [] simply means that E1[E2]=*((E1)+(E2)). So it does not matter whether E2 is positive or negative, and the compiler will take care of pointer type to generate the correct the result pointer (say, whether it is int or char). [1]

2. Negative indexing out of the bound

Things get complicated when we try to reference var a from var b, assuming that both a and b are next to each other…

#include <stdio.h>
#include <string.h>

int main()
	char a[10];
	char b[10];

	memset(a, 0x0, 10);
	memset(b, 0x1, 10);

	int i;
	printf("a=%p, b=%p\n", a, b);
	for (i = 0; i < 10; i++) {
		printf("b[%d]=%d, %p\n", i, b[i], &b[i]);
		printf("b[-%d]=%d, %p\n", i, b[-i], &b[-i]);

	return 0;

If you, like myself, expect to see some 0/1 interleaved, then the output would let you down:

[daveti@daveti c]$ ./negidx1
a=0x7ffc4c88ecd2, b=0x7ffc4c88ecc8
b[0]=1, 0x7ffc4c88ecc8
b[-0]=1, 0x7ffc4c88ecc8
b[1]=1, 0x7ffc4c88ecc9
b[-1]=0, 0x7ffc4c88ecc7
b[2]=1, 0x7ffc4c88ecca
b[-2]=0, 0x7ffc4c88ecc6
b[3]=1, 0x7ffc4c88eccb
b[-3]=0, 0x7ffc4c88ecc5
b[4]=1, 0x7ffc4c88eccc
b[-4]=0, 0x7ffc4c88ecc4
b[5]=1, 0x7ffc4c88eccd
b[-5]=0, 0x7ffc4c88ecc3
b[6]=1, 0x7ffc4c88ecce
b[-6]=64, 0x7ffc4c88ecc2
b[7]=1, 0x7ffc4c88eccf
b[-7]=6, 0x7ffc4c88ecc1
b[8]=1, 0x7ffc4c88ecd0
b[-8]=16, 0x7ffc4c88ecc0
b[9]=1, 0x7ffc4c88ecd1
b[-9]=0, 0x7ffc4c88ecbf

With all the addresses printed out, I guess you have figured sth out. The pitfall here is the actual memory layout of a and b – since stack grows downwards (from high to low), a has higher starting address than b. That is being said, b[-x] would never reach a, which can be seen from the addresses printed out. Therefore, if we wanna reference a from b, we need positive indexing out of bound, e.g.,

#include <stdio.h>
#include <string.h>

int main()
	char a[10];
	char b[10];

	memset(a, 0x0, 10);
	memset(b, 0x1, 10);

	int i;
	printf("a=%p, b=%p\n", a, b);
	for (i = 0; i < 20; i++) {
		printf("b[%d]=%d, %p\n", i, b[i], &b[i]);

	return 0;

And here is the output:

[daveti@daveti c]$ ./negidx2
a=0x7ffdbf9bc682, b=0x7ffdbf9bc678
b[0]=1, 0x7ffdbf9bc678
b[1]=1, 0x7ffdbf9bc679
b[2]=1, 0x7ffdbf9bc67a
b[3]=1, 0x7ffdbf9bc67b
b[4]=1, 0x7ffdbf9bc67c
b[5]=1, 0x7ffdbf9bc67d
b[6]=1, 0x7ffdbf9bc67e
b[7]=1, 0x7ffdbf9bc67f
b[8]=1, 0x7ffdbf9bc680
b[9]=1, 0x7ffdbf9bc681
b[10]=0, 0x7ffdbf9bc682
b[11]=0, 0x7ffdbf9bc683
b[12]=0, 0x7ffdbf9bc684
b[13]=0, 0x7ffdbf9bc685
b[14]=0, 0x7ffdbf9bc686
b[15]=0, 0x7ffdbf9bc687
b[16]=0, 0x7ffdbf9bc688
b[17]=0, 0x7ffdbf9bc689
b[18]=0, 0x7ffdbf9bc68a
b[19]=0, 0x7ffdbf9bc68b

Or, if we wanna reference b from a, we could use negative indexing out of bound, e.g.,

#include <stdio.h>
#include <string.h>

int main()
	char a[10];
	char b[10];

	memset(a, 0x0, 10);
	memset(b, 0x1, 10);

	int i;
	printf("a=%p, b=%p\n", a, b);
	for (i = 0; i < 10; i++) {
		printf("a[%d]=%d, %p\n", i, a[i], &a[i]);
		printf("a[-%d]=%d, %p\n", i, a[-i], &a[-i]);

	return 0;

And here is the output:

[daveti@daveti c]$ ./negidx3
a=0x7ffece838602, b=0x7ffece8385f8
a[0]=0, 0x7ffece838602
a[-0]=0, 0x7ffece838602
a[1]=0, 0x7ffece838603
a[-1]=1, 0x7ffece838601
a[2]=0, 0x7ffece838604
a[-2]=1, 0x7ffece838600
a[3]=0, 0x7ffece838605
a[-3]=1, 0x7ffece8385ff
a[4]=0, 0x7ffece838606
a[-4]=1, 0x7ffece8385fe
a[5]=0, 0x7ffece838607
a[-5]=1, 0x7ffece8385fd
a[6]=0, 0x7ffece838608
a[-6]=1, 0x7ffece8385fc
a[7]=0, 0x7ffece838609
a[-7]=1, 0x7ffece8385fb
a[8]=0, 0x7ffece83860a
a[-8]=1, 0x7ffece8385fa
a[9]=0, 0x7ffece83860b
a[-9]=1, 0x7ffece8385f9

3. Alignment

Things get more complicated when there is memory alignment in the stack, which is pretty common.

#include <stdio.h>
#include <string.h>

typedef struct _total_made_up {
	char c0;
	int i;
	char c1[10];
} tmu;

int main()
	tmu a;
	tmu b;

	memset(&a, 0x0, sizeof(tmu));
	memset(&b, 0x1, sizeof(tmu));

	int i;
	printf("a=%p, a.c0=%p, a.i=%p, a.c1=%p, sizeof(a)=%d\n",
		&a, &(a.c0), &(a.i), &(a.c1), sizeof(a));
	printf("b=%p, b.c0=%p, b.i=%p, b.c1=%p, sizeof(b)=%d\n",
		&b, &(b.c0), &(b.i), &(b.c1), sizeof(b));
	for (i = 0; i < 10; i++) {
		printf("a.c1[%d]=%d, %p\n", i, (a.c1)[i], &(a.c1)[i]);
		printf("a.c1[-%d]=%d, %p\n", i, (a.c1)[-i], &(a.c1)[-i]);

	return 0;

Here is the output:

[daveti@daveti c]$ ./negidx4
a=0x7ffc4bf3c8e0, a.c0=0x7ffc4bf3c8e0, a.i=0x7ffc4bf3c8e4, a.c1=0x7ffc4bf3c8e8, sizeof(a)=20
b=0x7ffc4bf3c8c0, b.c0=0x7ffc4bf3c8c0, b.i=0x7ffc4bf3c8c4, b.c1=0x7ffc4bf3c8c8, sizeof(b)=20
a.c1[0]=0, 0x7ffc4bf3c8e8
a.c1[-0]=0, 0x7ffc4bf3c8e8
a.c1[1]=0, 0x7ffc4bf3c8e9
a.c1[-1]=0, 0x7ffc4bf3c8e7
a.c1[2]=0, 0x7ffc4bf3c8ea
a.c1[-2]=0, 0x7ffc4bf3c8e6
a.c1[3]=0, 0x7ffc4bf3c8eb
a.c1[-3]=0, 0x7ffc4bf3c8e5
a.c1[4]=0, 0x7ffc4bf3c8ec
a.c1[-4]=0, 0x7ffc4bf3c8e4
a.c1[5]=0, 0x7ffc4bf3c8ed
a.c1[-5]=0, 0x7ffc4bf3c8e3
a.c1[6]=0, 0x7ffc4bf3c8ee
a.c1[-6]=0, 0x7ffc4bf3c8e2
a.c1[7]=0, 0x7ffc4bf3c8ef
a.c1[-7]=0, 0x7ffc4bf3c8e1
a.c1[8]=0, 0x7ffc4bf3c8f0
a.c1[-8]=0, 0x7ffc4bf3c8e0
a.c1[9]=0, 0x7ffc4bf3c8f1
a.c1[-9]=0, 0x7ffc4bf3c8df

If we compare the starting address of a and b, we can find a 32-byte difference. The size of the struct is 20 bytes, which means there is a 12-byte gap between the end of b and the start of a due to padding (alignment). Even worse, there is also padding happened within the structure, where the c0 is padded with 3 bytes to alignment with the 4-byte int (i), and c1 is padded with another 2 bytes in the end. Therefore, if we want to use a.c1 to reference b.c1 with negative indexing, the index should start from -22 (8 bytes in a, and 12 bytes in the gap, and 2 bytes padding in b.c1). You don’t see this number coming, do you:)

#include <stdio.h>
#include <string.h>

typedef struct _total_made_up {
	char c0;
	int i;
	char c1[10];
} tmu;

int main()
	tmu a;
	tmu b;

	memset(&a, 0x0, sizeof(tmu));
	memset(&b, 0x0, sizeof(tmu));
	b.c0 = 1;
	b.i = 1;
	memset(&b.c1, 0x1, 10);

	int i;
	printf("a=%p, a.c0=%p, a.i=%p, a.c1=%p, sizeof(a)=%d\n",
		&a, &(a.c0), &(a.i), &(a.c1), sizeof(a));
	printf("b=%p, b.c0=%p, b.i=%p, b.c1=%p, sizeof(b)=%d\n",
		&b, &(b.c0), &(b.i), &(b.c1), sizeof(b));
	for (i = 0; i < 10; i++) {
		printf("a.c1[%d]=%d, %p\n", i, (a.c1)[i], &(a.c1)[i]);
		printf("a.c1[-%d-22]=%d, %p\n", i, (a.c1)[-i-22], &(a.c1)[-i-22]);

	return 0;

[daveti@daveti c]$ ./negidx5
a=0x7ffce988ccf0, a.c0=0x7ffce988ccf0, a.i=0x7ffce988ccf4, a.c1=0x7ffce988ccf8, sizeof(a)=20
b=0x7ffce988ccd0, b.c0=0x7ffce988ccd0, b.i=0x7ffce988ccd4, b.c1=0x7ffce988ccd8, sizeof(b)=20
a.c1[0]=0, 0x7ffce988ccf8
a.c1[-0-22]=0, 0x7ffce988cce2
a.c1[1]=0, 0x7ffce988ccf9
a.c1[-1-22]=1, 0x7ffce988cce1
a.c1[2]=0, 0x7ffce988ccfa
a.c1[-2-22]=1, 0x7ffce988cce0
a.c1[3]=0, 0x7ffce988ccfb
a.c1[-3-22]=1, 0x7ffce988ccdf
a.c1[4]=0, 0x7ffce988ccfc
a.c1[-4-22]=1, 0x7ffce988ccde
a.c1[5]=0, 0x7ffce988ccfd
a.c1[-5-22]=1, 0x7ffce988ccdd
a.c1[6]=0, 0x7ffce988ccfe
a.c1[-6-22]=1, 0x7ffce988ccdc
a.c1[7]=0, 0x7ffce988ccff
a.c1[-7-22]=1, 0x7ffce988ccdb
a.c1[8]=0, 0x7ffce988cd00
a.c1[-8-22]=1, 0x7ffce988ccda
a.c1[9]=0, 0x7ffce988cd01
a.c1[-9-22]=1, 0x7ffce988ccd9

3. Summary

We have just talked about how messed up negative indexing could be on the stack. It is also possible to do this on the heap, which is more error-prone given the memory management under the hood (malloc/kmalloc). To correctly use negative (or out of bound) indexing, one needs to know exactly what the memory layout looks like, this could be hard for stack variables, even harder for heap ones. For normal programming, in most cases, you do not need negative indexing. As a matter of fact, the only normal usage I have seen so far is from ARMv3-M software development manual, where negative indexing is used to retrieve the SVC instruction number, which is saved on the stack by the CPU core during the supervisor call.


[1] https://stackoverflow.com/questions/3473675/are-negative-array-indexes-allowed-in-c

Posted in Programming | Tagged , | Leave a comment