How dangerous is the fact that SELinux is in "Permissive" mode? What should I be wary of? I have installed a certain ROM which comes with SELinux in "Permissive" mode. This is the only (good) ROM that properly fits my device and there is no way to change the state of SELinux.

Now I'm not really sure what are the consequences of such a decision and would be happy if someone could explain it to me (I have googled it and know what it is theoretically... just not in practice).
Said ROM has its root on "disabled" so the device is supposedly unrooted but how does that fits with the SELinux I'm not sure.
TL;DR: Feel free to jump directly to the conclusion at the bottom if you like :) !

SELinux goal is to prevent privilege escalation by enforcing a mandatory policy which restricts possible actions from both unprivileged and privileged users.

The term "users" here also includes any process running on the device, no matter if it is directly related to the physical user actions (the human, you ;) ), since every process is running using some system "user" account.

Historically, permissions on Unix-based systems are handled using what is called a Discretionary Access Control (DAC) system. In this model:


Resources like files have owners who can define access rights on the resources they own: this allows them to decide whether a particular resource should be private (only the owner can access it) or if it should be shared with some other users.
On top of this you have the super-user (called root on Unix-based systems) which is the administrative user and has access to everything on the system. This account can be used interactively by a human (typically a system administrator) to maintain or repair the device, but usually this account will mostly be used by background or low level services which require such privilege level: device drivers, network configuration services, services needing to access files from every users or handling internal inter-users communication.


This is very nice and already provides a good security. However, what about circumstances such as these:


What would happen if a bug in a service running as root is found which would allow an attacker to trick such service into running some arbitrary code? Such attacker would gain a complete access to the device. To give some concrete examples, such bug could be triggered by sending specially crafted network configuration information (DHCP) or a MMS to the phone.
What would happen if some user does not protect private resources correctly? Then these resources could be maliciously accessed (read, maybe even modified or deleted) by other unprivileged users. This is typically what you have when a malicious application is running on your phone (no matter if you have been tricked into installing it, or if it came here by-itself by using a bug in another unprivileged application, a browser or mail client for instance), and this malicious application tries to directly access other applications data or storage locations (it can do so to access normally unreachable data or to install itself in several places in order to make its removal harder).


Here comes SELinux.

SELinux is a Mandatory Access Control (MAC) system. While in the previously described DAC system users were responsible of setting appropriate right on their own resources, with a MAC system a system-wide policy (provided with the operating system) is enforced to both privileged and unprivileged users.

This solves the two issues mentioned above in the following ways:


As I said, this policy also applies to privileged users. This means that, with a properly designed policy, a service designed to handle the device's network configuration will be unable to do anything else: it will have no access to SMS for instance, and a service handling SMS will have no access to the network configuration, and neither of them will have access to the user's data, despite the fact that both are running using the super-user account.
Android recently included a multi-user feature which is enforced by SELinux, preventing any user from accessing other user's data. But beyond that, SELinux policy is also responsible from describing permitted applications behavior, and most likely even if some resources are not properly protected using the DAC system SELinux will come at the rescue and still prevent the malicious application from directly access them.


The DAC and MAC systems are not mutually exclusive, on the contrary the MAC system (SELinux) acts as a second layer of defense behind the DAC system (the traditional Unix-like permissions). The job of SELinux is to block any activity contrary to the policy which, given only the DAC system, would otherwise be accepted.

The tricky thing is that such policy can be very complex to write: it must indeed cover every device's components for every possible usage in every situation. In fact, no matter if some action may be legitimate in your situation: if it is not in the policy, it is forbidden. Poorly designed policies can therefore have random consequences, like application crashes, unusable functionality, and so on.

That's why the first versions of Android shipping SELinux included it in "Permissive" mode by default. In this mode, SELinux will log policy violations, but it will not attempt to block the associated activity. By analyzing the resulting log files, it becomes possible to correct and enhance the policy up to the point when the only remaining policy violation are indeed malicious or undesired behaviors. At this point, SELinux can be turned into "Enforcing" mode: it will now not only log but also block every offending action.

Conclusion

SELinux is a mitigation technique. It does not prevent attackers from entering into your phone, but it ensures that once there they can do as few things as possible, ideally nothing useful thus removing any interest of attacking the phone in the first place.

The older the ROM, the larger the number of security bugs which would open such access. SELinux would be an efficient way to keep a minimum of safety despite these known vulnerabilities, however to function properly SELinux relies on a complex policy.

If your ROM is provided with SELinux in "Permissive" mode by default, this likely means that the policy it contains is not reliable enough to be safely switched into "Enforcing" mode.

If you are techie enough and have access to the phone log (dmesg at least, but usually they are also copied into logcat: there are applications allowing to see the latter one but depending on your Android version they may require root access), you can check if you find "avc" entries: these are messages telling you that SELinux has just detected an action going against the policy.

Here is an example of such entry taken from CyanogenMod's website:

type=AVC msg=audit(1363289005.532:184): avc: denied { read } for pid=29199 comm="Trace" 
name="online" dev="sysfs" ino=30 scontext=staff_u:staff_r:googletalk_plugin_t 
tcontext=system_u:object_r:sysfs_t tclass=file


If there is none, just a few of them or for any reason you think they may not keep you from using the phone, you may try to switch SELinux into "Enforcing" mode. In older CyanogenMod ROMs, this was easy and possible simply using an hidden option in the GUI (no need to root the phone or install any specific application), I don't know if other ROMs offered the same feature but since you used the CyanogenMod tag I suppose you may be lucky ;).