Is it normal to have no publications after 2.5 years in a PhD program?
I was in the exact same situation (also CS) and I would say that it is both normal and cause for concern. So there's no reason to take it personally, or to start worrying about your abilities, this happens to many people, but it is a situation that needs to be resolved. From now on, your number one priority should be to get a paper, put everything else on hold. Don't worry about getting enough papers, worry about getting one.

You have something under submission, so the odds are you'll get it accepted somewhere pretty soon. However, if you don't, I would recommend trying to find someone with experience who can coach you hands-on. Find someone who can read your draft in detail and tell you what needs to be done. 2.5 years with no publications is usually a sign that the supervisor is not paying very close attention, and it may be good to find someone who can pay close attention to you, at least for a bit. Getting a paper past reviewers is a strange, dark art, and it really helps to get some intense supervision for your first attempt.

edit after comment: Two further tips to help your situation:


Idea generation is a skill and you can work on getting better at it. 
[1 2 3]. If you're not generating ideas, tackle that problem head-on. Don't think of yourself as a non-creative person, and don't blame your subject: there are always exciting directions if you look hard enough.
Try to write a collaborative paper, ask a postdoc or a fellow PhD in your group to do some brainstorming, and to find an idea that you can work on together. That way, the work becomes less lonely, and you have at least one other person who cares about it. It might be a little scary to initiate something like this, but if the alternative is working by yourself for the next 2.5 years, you may consider stepping out of your comfort zone a little bit.